## A Counting Problem

View as PDF

Points: 15
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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