Как известно, в Берляндии ровно две проблемы — дураки и дороги. Кроме того, в Берляндии есть n городов, в которых эти дураки живут, а дороги, соответственно, эти города соединяют. Все берляндские дороги двунаправленные. Так как в Берляндии дураков много, то для каждой пары городов есть путь между ними (иначе дураки расстроятся), а также между каждой парой городов есть не более одного простого пути (иначе дураки заблудятся).
Но это еще не все особенности Берляндии. В этой стране дураки иногда ходят друг к другу в гости, и от этого дороги портятся. Дураки не очень умны, поэтому всегда ходят только по простым путям.
Простой путь — это путь, который проходит через каждый город Берляндии не более одного раза.
Правительству Берляндии известны пути, по которым ходят дураки. Помогите правительству для каждой дороги посчитать, сколько различных дураков может по ней проходить.
Обратите внимание на то, как заданы пути дураков во входных данных.
Выходные данные
Выведите n - 1 целое число. Числа должны быть разделены пробелами. i-e число должно быть равно количеству дураков, которые могут проходить по i-той дороге. Дороги нумеруются с единицы в порядке их следования во входных данных.
Примечание
В первом примере дурак номер 1 пройдет через первую и третью дорогу, а дурак номер 3 — через вторую, первую и четвертую.
Во втором примере через первую дорогу пройдут дураки под номерами 1, 3 и 5, через вторую — дурак номер 5, через третью — дурак номер 3, через четвертую — дурак номер 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
1 3
2 4
2 5
2
1 4
3 5
|
2 1 1 1
|
|
2
|
5
3 4
4 5
1 4
2 4
3
2 3
1 3
3 5
|
3 1 1 1
|