Find the isolated stations

Scenario

A city metro has n stations, numbered 0 to n - 1. A track joins two stations, and trains run on it in both directions. The list of tracks is [a, b] pairs.

Some stations have no track at all, for example because a line is closed for works. You work on the route planner, and it must warn riders about these isolated stations.

Your task

Write isolated_stations(n, tracks).

n is the number of stations.
tracks[i] = [a, b] is a track between two different stations. A track can be listed more than once.
Return the numbers of all stations that no track touches, from the smallest to the largest. Return an empty list when every station has a track.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 6, tracks = [[0, 1], [1, 2], [4, 2]]
Output: [3, 5]

Station	Tracks that name it	Isolated?
0	`[0, 1]`	no
1	`[0, 1]`, `[1, 2]`	no
2	`[1, 2]`, `[4, 2]`	no
3	none	yes
4	`[4, 2]`	no
5	none	yes

Stations 3 and 5 have no track.

Example 2#

text2 lines

Input:  n = 3, tracks = []
Output: [0, 1, 2]

There are no tracks, so every station is isolated.

Example 3#

text2 lines

Input:  n = 2, tracks = [[0, 1]]
Output: []

One track touches both stations, so no station is isolated.

Constraints

1 ≤ n ≤ 10^5
0 ≤ length of tracks ≤ 2 · 10^5
0 ≤ a, b < n and a ≠ b for every track

What does n ≤ 10^5 tell you?

There can be 100,000 stations and 200,000 tracks. Scanning every track for each station would be about twenty billion steps, far too slow.

Each track names two stations. Reading the tracks once and marking the stations they name is enough.

Scenario

A city metro has n stations, numbered 0 to n - 1. A track joins two stations, and trains run on it in both directions. The list of tracks is [a, b] pairs.

Some stations have no track at all, for example because a line is closed for works. You work on the route planner, and it must warn riders about these isolated stations.

Your task

Write isolated_stations(n, tracks).

n is the number of stations.
tracks[i] = [a, b] is a track between two different stations. A track can be listed more than once.
Return the numbers of all stations that no track touches, from the smallest to the largest. Return an empty list when every station has a track.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 6, tracks = [[0, 1], [1, 2], [4, 2]]
Output: [3, 5]

Station	Tracks that name it	Isolated?
0	`[0, 1]`	no
1	`[0, 1]`, `[1, 2]`	no
2	`[1, 2]`, `[4, 2]`	no
3	none	yes
4	`[4, 2]`	no
5	none	yes

Stations 3 and 5 have no track.

Example 2#

text2 lines

Input:  n = 3, tracks = []
Output: [0, 1, 2]

There are no tracks, so every station is isolated.

Example 3#

text2 lines

Input:  n = 2, tracks = [[0, 1]]
Output: []

One track touches both stations, so no station is isolated.

Constraints

1 ≤ n ≤ 10^5
0 ≤ length of tracks ≤ 2 · 10^5
0 ≤ a, b < n and a ≠ b for every track

What does n ≤ 10^5 tell you?

There can be 100,000 stations and 200,000 tracks. Scanning every track for each station would be about twenty billion steps, far too slow.

Each track names two stations. Reading the tracks once and marking the stations they name is enough.