Given a bidirectional tree containing ~N~ 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 ~a~ to ~b~ is different from a path from ~b~ to ~a~.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~, the number of nodes.

The next ~N-1~ lines will each contain ~2~ integers, ~a, b~ ~(1 \le a, b \le N)~, indicating node ~a~ and node ~b~ 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