Старое дерево знаний состоит из n узлов, соединённых ветвями так, что между любыми двумя узлами существует ровно один путь.

Один из узлов, r, считается исходным уровнем дерева. Для каждого узла нужно определить его уровень относительно r.

Уровень узла — это количество ветвей на простом пути от узла r до данного узла.

Требуется для всех узлов дерева найти их уровни относительно узла r.

Входные данные

В первой строке заданы два целых числа n и r — количество узлов дерева знаний и номер исходного узла.

В следующих n - 1 строках заданы ветви дерева. Каждая строка содержит два целых числа u и v, означающие, что узлы u и v соединены ветвью.

Выходные данные

Выведите n целых чисел — уровни узлов относительно узла r для узлов 1, 2, ..., n в этом порядке.

Ограничения

• 1 <= n <= 100000
• 1 <= r <= n
• 1 <= u, v <= n
• Описанный граф является деревом.

Примеры

Пример 1

Входные данные

3 2
1 2
2 3

Выходные данные

1 0 1

Пример 2

Входные данные

4 1
1 2
1 3
1 4

Выходные данные

0 1 1 1