На уроке химии Андрей узнал, что насыщенные углеводороды (алканы) вступают в реакцию радикального хлорирования. При этом образуется смесь различных хлорпроизводных. Андрей — очень любопытный мальчик, поэтому его заинтересовало, сколько существует различных монохлорпроизводных для заданного алкана. Для небольших молекул Андрей легко справился с этой задачей, но с большими молекулами у него возникли трудности, поэтому он попросил вас решить эту задачу.
Формально, вам дано дерево, состоящее из n вершин, такое что степень каждой вершины не превосходит 4. Требуется посчитать количество различных с точностью до изоморфизма деревьев, которые можно получить путем добавления к данному дереву одной вершины и одного ребра так, чтобы граф оставался деревом и степень каждой вершины не превосходила 4.
Два дерева называются изоморфными, если существует биекция f(v), такая что вершины u и v соединены ребром, если и только если вершины f(v) и f(u) соединены ребром.
Выходные данные
Выведите одно число — ответ на задачу.
Примечание
В первом примере к каждой вершине можно добавить новую, но при этом деревья, полученные добавлением новой вершины к вершинам 1, 3, 4 будут изоморфными, поэтому ответ 2.
Во втором примере к первой вершине добавить новую вершину нельзя так как степень вершины уже равна четырем. А все деревья, полученные добавлением новой вершины к вершинам 2, 3, 4, 5 будут изоморфными, поэтому ответ 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
2 3
2 4
|
2
|
|
2
|
5
1 2
1 3
1 4
1 5
|
1
|
|
3
|
5
2 5
5 3
4 3
4 1
|
3
|