Competitions

# Depth First Search

# 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.

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