eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #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