Canmuu и друзья раздобыли большой запас плутония и решили закопать новое сокровище на перекрёстке в глубине канадской глуши. Для сокровища нужна карта, и они создадут свою.
Сеть имеет $N$ $(4 \le N \le 100,000)$ перекрёстков (номера $1..N$) и $N$ дорог. Оживлённые перекрёстки всех путают, поэтому у каждого от одной до четырёх дорог. Отличное обслуживание позволяет лосю бегать в обе стороны между любыми двумя перекрёстками. Canmuu не закопает плутоний на четырёхстороннем перекрёстке: трафик уменьшает секретность.
Карта содержит все дороги и перекрёстки, но ради тайны отмечен только перекрёсток с сокровищем, конечно большим красным 'X'.
Бдительный лось Canmuu нарисовал пробные карты для разных мест. Он заметил, что два места могут дать похожие карты. Заинтересовавшееся стадо решило узнать число разных карт.
Карты одинаковы, если существует соответствие, при котором:
перекрёстки с X соответствуют друг другу;
другим перекрёсткам можно задать соответствие так, что
после выбора соответствия перекрёстков соединяющие их дороги тоже соответствуют.
Пример ниже с $N = 4$: сокровище может быть на любом из четырёх перекрёстков.
+ + X +
/| /| /| /|
X---+ | +---X | +---+ | +---+ |
\| \| \| \|
+ + + XПоследние две карты одинаковы: можно сопоставить вершины (переверните рисунок), тогда дороги точно совпадают. Разных карт лишь три.
Сколько разных карт возможно для данного набора дорог?
*Первые 10 отправок в этой задаче получат дополнительные отзывы.
Входные данные
Читайте со стандартного ввода.
Строка 1: одно целое $N$.
Строки 2..$N + 1$: два целых $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$ через пробел — дорога между $A$, $B$.
Выходные данные
Пишите в стандартный вывод.
- Строка 1: одно целое, число разных карт сокровища.
Примеры
Входные данные 1
4 1 2 2 3 3 1 1 4
Выходные данные 1
3
Примечание
Рисунок дорог и перекрёстков:
4---1---2
\ /
3Сокровище можно закопать везде, но перекрёстки 2 и 3 дают одинаковые карты. Итого разных карт 3.
Автор задачи: Yang Yi, 2007