409452: GYM103562 G Radiant Ruby

As Valentine's Day approaches, Harmony wants to get a gift for her sweetheart. Specifically, she has in mind to buy a brilliant ruby gemstone, representing her heart. When she goes to look at different rubies at the jewelry store, Harmony sees that each one is cut uniquely with a different number and arrangement of facets. In fact, each stone can be represented as a binary tree that has been reflected and connected with edges across the leaves, producing a symmetrical pattern of connected facets.

In order to select the best ruby out of the available stones, Harmony comes up with a metric for the quality of a ruby. A ruby's radiance is equal to the number of unique cycles which can be found within its facet pattern. Write a program to help Harmony evaluate radiance and select the finest ruby!

The first line of input contains an integer $$$V$$$ ($$$2 \leq V \leq 10^6$$$) denoting the number of vertices in the binary tree representing a ruby's facet pattern. $$$V - 1$$$ lines follow, each containing two space-separated integers $$$u$$$ and $$$v$$$ which represent endpoints for an edge in the tree (in general, any tree with $$$n$$$ vertices has exactly $$$n - 1$$$ edges). You are also given that $$$u$$$ is a parent of $$$v$$$ in the tree, and the tree will always be rooted at the first vertex $$$1$$$.

Print the number of unique cycles which can be found in the graph generated by connecting each leaf vertex in the binary tree to its equivalent in a reflected copy of the tree.

11
1 9
5 3
2 7
1 5
9 2
8 10
2 8
5 4
3 6
3 11

10