Competitions

# Depth First Search

# Depth First Search - Timestamps

Undirected graph is given. Run depth first search from the given vertex **v**. Print the timestamps **d**[**v**] and **f**[**v**] for each vertex **v** in the increasing order of vertices.

#### Input

First line contains number of vertices **n** (**n** ≤ **100**) and edges **m** of undirected graph. Each of the next **m** lines contains two vertices **a** and **b** - an undirected edge of the graph. The last line contains vertex **v**.

#### Output

Run **dfs**(**v**). Print the timestamps **d**[**v**] and **f**[**v**] for each vertex **v** (**v** = **1**, **2**, ..., **n**). The timestamps for each vertex must be printed in a separate line.

Input example #1

3 3 1 2 2 3 1 3 2

Output example #1

2 5 1 6 3 4

Input example #2

5 5 1 2 2 3 2 5 2 4 1 4 3

Output example #2

3 6 2 9 1 10 4 5 7 8