Depth first search on a disconnected graph

Undirected disconnected graph is given. Run depth first search on it. For each vertex print the timestamps when it becomes gray / black in the order of their first visit.

Input

First line contains number of vertices n (n ≤ 100) of undirected graph. Each next line contains two vertices a and b - an undirected edge of the graph.

Output

Run depth first search on a graph. For each vertex print the timestamps when it becomes gray / black in the order of their first visit.

Examples