e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

April 25 - ADA Contest

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 (n100) 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.

prb9654.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
1 2
5 6
2 4
1 4
Output example #1
Vertex: 1, Gray 1, Black 6
Vertex: 2, Gray 2, Black 5
Vertex: 4, Gray 3, Black 4
Vertex: 3, Gray 7, Black 8
Vertex: 5, Gray 9, Black 12
Vertex: 6, Gray 10, Black 11
Author Michael Medvedev