Точки з'єднання - розстановка міток

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

Вхідні дані

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

Вихідні дані

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

Приклади

Примітка

Використовуйте матрицю суміжності для зберігання графа.