Single points of failure: hints, no solution

A transit network has n stations numbered from 0 to n - 1 and two-way links between them. Each row of links joins two different stations, and no pair is listed twice. The network need not be connected.

A station is a single point of failure if closing it, together with all of its links, leaves the remaining stations in more separate connected parts than the network had before. Closing a station that is a dead end, or one that is alone, does not do that.

Return the ids of all single points of failure in ascending order, or an empty list if there are none. Networks can contain long chains of stations, so make sure the search does not depend on deep recursion, and aim for time linear in stations plus links.

Examples

Input

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

Output

[1, 2, 3]

Note

Closing 1, 2 or 3 splits the line of stations into two pieces; the ends are dead ends.

Input

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

Output

[]

Note

Every station lies on a ring, so closing any one of them keeps the rest connected.

Input

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

Output

[2]

Note

Station 2 is the only link between the two triangles; closing it separates them.

Constraints

• 1 <= n <= 16000
• 0 <= links.length <= 20000
• No link joins a station to itself and no pair is repeated
• The network may be disconnected

Hint 1: a nudge

When you close one station, which stations could lose their way to the rest? Think about a station whose neighbours all have another way round, and one where some neighbour does not.

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