Under construction

Still being built. Things may change

Graph Stem

Interview

Time limit1sMemory limit512 MB

Summary
Given a tree, repeatedly strip all leaves at once until two or fewer leaves remain, then output the surviving vertices in ascending order.
Level

Medium5 of 10

Topics
Tree, Graph, BFS, Queue
Solved
No attempts yet

Problem

In a graph, a cycle is a path from a vertex back to the same vertex that repeats no edge and has length not equal to 00.

You are given a graph with no cycles.

Among the vertices of this graph, a vertex with exactly one incident edge is called an edge vertex.

Repeatedly delete all edge vertices at the same time. Once the graph becomes a straight line, the set of vertices that remain is called the stem of the graph. If the number of edge vertices is two or fewer, the graph is considered a straight line.

For the graph in the figure above, the edges connected to edge vertices are marked in red below.

Cutting the connections of the edge vertices attached to the red edges leaves the stem of the graph, connected in a straight line as in the figure below. Once the graph has become a straight line, no more edge vertices are deleted even if some remain.

Write a program that finds the vertices forming the stem of the graph.

Input

The first line of input gives the number of vertices NN in the initial graph. (2≤N≤100 000)(2 \le N \le 100\,000)

The next N−1N-1 lines give the numbers a,ba, b of the two vertices connected by each edge. (0≤a, b<N, a≠b)(0 \le a,\ b < N,\ a \ne b)

Output

On the first line of output, print the numbers of the vertices forming the stem of the graph in ascending order, separated by spaces.

Hint

The stem of the graph contains at least one vertex.

Examples2

  1. Example 1

    Input
    10
8 4
4 1
8 5
4 9
5 6
6 2
5 0
8 7
2 3
    Expected output
    2 4 5 6 8

  2. Example 2

    Input
    10
0 2
6 5
6 4
1 9
0 1
0 6
0 8
6 7
1 3
    Expected output
    0 1 6