Дано дерево, состоящее из \(n\) вершин. Гусеница обозначается парой целых чисел \((p, q)\) (\(1 \leq p, q \leq n\), \(p \neq q\)): её голова находится в вершине \(p\), её хвост находится в вершине \(q\), и она доминирует над всеми вершинами на простом пути от \(p\) до \(q\) (включая \(p\) и \(q\)). Гусеничная последовательность пары \((p, q)\) определяется как последовательность, состоящая только из вершин на простом пути, отсортированных в порядке возрастания расстояния до \(p\).
Нора и Арон по очереди двигают гусеницу, причем Нора ходит первой. Оба игрока будут использовать свою собственную оптимальную стратегию:
- Они будут играть, чтобы выиграть;
- Однако, если это невозможно, они будут играть, чтобы помешать другому человеку победить (таким образом, игра закончится ничьёй).
В свой ход Нора может выбрать вершину \(u\), смежную с вершиной \(p\), над которой не доминирует гусеница, и переместить все вершины в ней на одно ребро по направлению к вершине \(u\)\(^{\text{∗}}\). В свою очередь, Арон может выбрать вершину \(v\), смежную с вершиной \(q\), над которой не доминирует гусеница, и переместить все вершины в ней на одно ребро по направлению к вершине \(v\). Обратите внимание, что ходы, разрешенные двум игрокам, различны.
Если \(p\) — лист\(^{\text{†}}\), то Нора выигрывает\(^{\text{‡}}\). Если \(q\) — лист, то Арон выигрывает. Если либо изначально оба \(p\) и \(q\) являются листьями, либо после \(10^{100}\) ходов игра не закончится, результатом будет ничья.
Пожалуйста, посчитайте количество целочисленных пар \((p, q)\) с \(1 \leq p, q \leq n\) и \(p \neq q\) таких, что если изначально гусеница находится на \((p, q)\), то Арон выиграет.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую целое число: количество целых пар \((p, q)\), для которых Арон выиграет.
Примечание
В первом наборе входных данных всеми возможными гусеницами являются \((1, 2)\) и \((2, 1)\), что приводит к ничьей с самого начала, поскольку оба \(p\) и \(q\) являются листьями.
Во втором наборе входных данных, гусеницы, которые позволяют Арону выиграть, следующие: \((1, 3)\), \((1, 4)\), \((1, 5)\), \((2, 3)\), \((2, 4)\), \((2, 5)\). Давайте рассмотрим некоторых гусениц.
- Для гусеницы \((1, 5)\): вершина \(p = 1\) — это не лист, но вершина \(q = 5\) — лист, так что Арон выигрывает в самом начале.
- Для гусеницы \((2, 1)\): вершина \(p = 2\) не является листом, и \(q = 1\) не является листом. На первом ходу Нора может переместить гусеницу в направлении вершины \(5\). Следовательно, гусеница становится \((5, 2)\), а вершина \(p = 5\) — лист, так что Нора выиграет.