Bare paths in a binary tree

Two nodes x and y in a binary rooted tree are said to be neighbours if x is a parent of y or y is a parent of x. The degree of a node is the number of its neighbours. A path of length N in a binary rooted tree is a sequence of nodes (x₁, x₂, ..., x_N), in which x_k is a neighbour of x_k+1 for each k = 1, 2, ..., N−1. Also, no node can appear in a path more than once.
We say that a path is a bare path if the degree of all nodes in the path is at most 2.

     

Image 1. Examples of binary rooted trees with all their longest bare paths. The nodes in the longest bare paths are highlighted in black. Case a) depicts Example 1 and case b) depicts Example 2 below.

The task

You are given a binary rooted tree. Find the length and the total number of longest bare paths in the tree.

---

Input

The first input line contains two integers N and R separated by space. The values indicate (in this order) the number of nodes in the tree and the label of the root. The nodes are labeled by integers 0, 1, ..., N−1. Next, there are M text lines, each describe one pair of neighbour nodes. The line contains the labels of the nodes separated by space. The order of nodes in the pair and the order of pairs of nodes in the input is arbitrary.
It holds, 1 ≤ N ≤ 10⁶.

Output

The output contains one text line with two integers separated by space. The first integer represents the length of a longest bare path in the given tree, the second integer represents the number of all longest bare paths in the tree.

Example 1

Input

16 7
1 0
2 1
2 3
3 4
4 5
6 2
7 6
7 8
8 15
9 11
11 10
12 9
13 12
13 14
15 13

Output

4 2

The data and solution of Example 1 are depicted in Image 1a).

Example 2

Input

20 9
0 1
2 0
3 2
3 7
7 4
4 6
6 5
7 8
9 3
9 10
10 13
12 11
13 12
13 14
14 19
16 15
16 17
18 16
19 18

Output

3 3

The data and solution of Example 2 are depicted in Image 1b).

Example 3

Input

7 3
1 0
1 2
3 1
3 5
5 4
5 6

Output

1 5

When the tree is regular and perfectly balanced and contains more than 3 nodes then each leaf and also the root represents one longest bare path of length 1. In such case, the number of longest bare paths is (N+3)/2.

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set