Given a bidirectional tree containing nodes, output the number of paths of odd length, and number of paths of even length. A path is of odd length if it contains an odd number of edges, and even length if it contains a positive even number of edges. A path is different from another path if the starting or ending nodes differ. For example, a path from to is different from a path from to .
Input Specification
The first line will contain the integer , the number of nodes.
The next lines will each contain integers, , indicating node and node are connected by an edge. It is guaranteed the entire tree is connected.
Output Specification
On the first line, output the number of even length paths.
On the second line, output the number of odd length paths.
Sample Input
5
1 3
2 3
4 3
4 5
Sample Output
8
12
Comments
This is an easier version of this problem: https://dmoj.ca/problem/aac1p5 (that problem you need to minimize the difference between the number of even and odd paths among all paths by changing the length of at most 1 of the weighted paths in the tree)