Dead-end stations: hints, no solution

A transit map has n stations numbered from 0 to n - 1. Each row of links joins two different stations, and the same pair may be listed more than once. A dead-end station is connected to exactly one other station, no matter how many times that pair is listed. A station with no links at all is not a dead end.

Return the ids of all dead-end stations in ascending order. If there are none, return an empty list.

Examples

Input

n = 5, links = [[0, 1], [1, 2], [1, 3], [3, 4]]

Output

[0, 2, 4]

Note

Stations 0, 2 and 4 each have one distinct neighbour; station 1 has three and station 3 has two.

Input

n = 3, links = [[0, 1], [0, 1], [1, 2]]

Output

[0, 2]

Note

The pair 0 and 1 is listed twice but still counts as one neighbour, so station 0 is a dead end; station 1 has two neighbours.

Input

n = 3, links = [[0, 1], [1, 2], [2, 0]]

Output

[]

Note

In a triangle every station has two neighbours, so the list is empty.

Constraints

• 1 <= n <= 100000
• 0 <= links.length <= 100000
• Every link joins two different stations in the range 0 to n - 1

Hint 1: a nudge

For a single station, what would you need to know about the stations next to it before you could say it is a dead end? Does listing the same pair twice change that answer?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing