Minimizing Inconvenience in Z Country

Z Country is located on a far‐away magical eastern peninsula. Under the rule of Little Z, roads have been the main mode of transportation connecting its N cities. Some cities are connected by bidirectional roads. It is known that no two cities share the same longitude and that each city is directly connected by a road to at most one city lying to its east. The capital is the center of politics, economy, culture, and tourism so that every day thousands of people from other cities travel to the capital.

To make transportation more convenient, Little Z plans to convert some roads into railways along planning routes. A planning route is defined as a sequence of cities (of length at least 2) with no city repeated such that every pair of adjacent cities is directly connected by a road; all the roads in the chosen sequence will be rebuilt as railway. Moreover, each city may appear in at most one planning route (that is, any two planning routes must be vertex–disjoint).

Since not all roads are converted, a traveler may have to take both train and long–distance buses to reach the capital. Buses can only travel along roads (i.e. between two directly connected cities that are not on a planning route), while trains run along the railway segments. For any city, its inconvenience value is defined as the number of bus rides needed to go from that city to the capital (note that the capital’s inconvenience value is 0).

Little Z wants to choose planning routes so that the traffic system’s inconvenience value is minimized, and he is also interested in the number of different planning routes selections that achieve this minimum. (Note that a planning route such as 1-2-3 is regarded as equivalent to its reverse 3-2-1; two schemes are considered different if and only if there exists a planning route that is present in one scheme but not in the other.)

Formally, consider an undirected tree (since the road network in Z Country is connected and, by the given property, it is a tree) with N nodes labeled 1 through N where the cities are arranged in increasing order of longitude (that is, city 1 is the westernmost and city N is the easternmost – the capital). For each edge that is not converted to railway, a bus ride is needed when travelling from one city to the capital along the unique simple path. If an edge is rebuilt as railway (by being chosen in some planning route) then no bus ride is needed for that segment. However, planning routes must be vertex–disjoint and each railway segment must come from a contiguous segment of the unique path from some city to the capital. Let the inconvenience value of a city be the number of bus segments along its path to the capital; the inconvenience value of the transportation system is the maximum such value among all cities. Your task is to determine the minimum possible inconvenience value and the number of planning–route selection schemes that achieve it, modulo a given integer Q.

The road network is given in the following format. There are exactly N cities (numbered 1 to N) and exactly N−1 roads. Each road connects two cities. It is guaranteed that for every road connecting cities u and v, one of them (say, the one with the smaller label) is to the west of the other. The capital is city N.

Input (Input Format):
The first line contains two integers N and Q separated by a space. Each of the next N−1 lines contains two integers u and v indicating that there is a road between cities u and v.

Output (Output Format):
Output two integers separated by a space: the minimum inconvenience value and the number of planning route selection schemes that achieve that inconvenience value, taken modulo Q.

Note on Formulas:
All formulas should be represented in LaTeX format. For example, the inconvenience value of a city is defined as $$\text{inconvenience} = \text{\# of bus rides}.$$

inputFormat

The first line contains two integers N and Q (\(2 \leq N \leq \text{some limit}\), \(Q \geq 1\)). The following N-1 lines each contain two integers u and v (\(1 \le u, v \le N\)), representing a bidirectional road between cities u and v. It is guaranteed that in each pair, the smaller number corresponds to the city lying to the west, and the capital is city N (the easternmost).

Sample Input:
3 100
1 2
2 3

outputFormat

Output two integers separated by a space: the minimum possible inconvenience value and the number of different planning route selection schemes achieving that value, modulo Q.

Sample Output:
0 1

sample

3 100
1 2
2 3

0 1