D. Андрей и задача по химии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На уроке химии Андрей узнал, что насыщенные углеводороды (алканы) вступают в реакцию радикального хлорирования. При этом образуется смесь различных хлорпроизводных. Андрей — очень любопытный мальчик, поэтому его заинтересовало, сколько существует различных монохлорпроизводных для заданного алкана. Для небольших молекул Андрей легко справился с этой задачей, но с большими молекулами у него возникли трудности, поэтому он попросил вас решить эту задачу.

Формально, вам дано дерево, состоящее из n вершин, такое что степень каждой вершины не превосходит 4. Требуется посчитать количество различных с точностью до изоморфизма деревьев, которые можно получить путем добавления к данному дереву одной вершины и одного ребра так, чтобы граф оставался деревом и степень каждой вершины не превосходила 4.

Два дерева называются изоморфными, если существует биекция f(v), такая что вершины u и v соединены ребром, если и только если вершины f(v) и f(u) соединены ребром.

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

В первой строке входных данных задано число n (1 ≤ n ≤ 100 000) — количество вершин в дереве.

В следующих n - 1 строках содержатся описания рёбер. Каждое ребро описывается двумя числами ui и vi (1 ≤ ui, vi ≤ n) — номерами вершин, соединёнными данным ребром. Гарантируется, что заданный граф является деревом, и степень каждой вершины не превышает 4.

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

Выведите одно число — ответ на задачу.

Примеры
Входные данные
4
1 2
2 3
2 4
Выходные данные
2
Входные данные
5
1 2
1 3
1 4
1 5
Выходные данные
1
Входные данные
5
2 5
5 3
4 3
4 1
Выходные данные
3
Примечание

В первом примере к каждой вершине можно добавить новую, но при этом деревья, полученные добавлением новой вершины к вершинам 1, 3, 4 будут изоморфными, поэтому ответ 2.

Во втором примере к первой вершине добавить новую вершину нельзя так как степень вершины уже равна четырем. А все деревья, полученные добавлением новой вершины к вершинам 2, 3, 4, 5 будут изоморфными, поэтому ответ 1.