e-olymp
Змагання

ADA Classes - Depth First Search

Пошук у глибину - розстановка міток

Дано неорієнтований граф. Запустіте пошук у глибину із заданої вершини v. Виведіте мітки d[v] і f[v] для кожної вершини v в порядку зростання вершин.

Вхідні дані

Перший рядок містить кількість вершин n (n100) і ребер m неорієнтоаного графа. Вершини нумеруються починаючи з 1. Кожен з наступних m рядків містить дві вершини a і b - неорієнтоване ребро графа. Наступний рядок містить вершину v.

Вихіні дані

Запустіть dfs(v). Виведіть міткии d[v] і f[v] для кожної вершини v (v = 1, 2, ..., n). Мітки для кожної вершини потрібно виводити в окремому рядку.

prb8761.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 3
1 2
2 3
1 3
2
Вихідні дані #1
2 5
1 6
3 4
Вхідні дані #2
5 5
1 2
2 3
2 5
2 4
1 4
3
Вихідні дані #2
3 6
2 9
1 10
4 5
7 8