Country Z is located on a remote and magical eastern peninsula. During the reign of Little Z, highways were the primary means of transportation. Country Z has $n$ cities, and some cities are connected by bidirectional highways. Remarkably, every city in Country Z has a unique longitude, and each city is directly connected by a highway to at most one city located to its east. The capital of Country Z is the center of its politics, economy, culture, and tourism, and thousands of people travel from other cities to the capital every day.

To make transportation in Country Z more convenient and smooth, Little Z decided to designate several planned routes in the highway system and convert all highways within these routes into railways.

We define each planned route as a sequence of cities with a length greater than 1, where each city appears at most once in the sequence, and adjacent cities in the sequence are directly connected by a highway (to be converted into a railway). Furthermore, each city can appear in at most one planned route; that is, any two planned routes cannot share any common parts.

Of course, in general, it is impossible to convert all highways into railways. Therefore, from some cities, one still needs to take a long-distance bus to reach the capital. Long-distance buses only travel between adjacent cities connected by highways. Thus, to travel from a certain city to the capital, one may need to continuously transfer between long-distance buses and trains.

We define the "inconvenience value" of a city as the number of times one needs to take a long-distance bus to travel from that city to the capital. The "inconvenience value" of Country Z's transportation system is the maximum of the inconvenience values of all cities. Obviously, the "inconvenience value" of the capital is 0. Little Z wants to know how to determine the planned routes to convert into railways such that the "inconvenience value" of Country Z's transportation system is minimized, and how many different ways of choosing the planned routes achieve this minimum "inconvenience value". Of course, the total number of ways may be very large, and Little Z only cares about the value modulo $Q$.

Note: The planned route 1-2-3 and the planned route 3-2-1 are equivalent, meaning that reversing a planned route is still considered equivalent. Two schemes are different if and only if one scheme contains a planned route that does not belong to the other scheme.

Input

The first line of the input file contains three positive integers $N$, $M$, and $Q$, where $N$ represents the number of cities, $M$ represents the total number of highways, and the $N$ cities are numbered from 1 to $N$, with 1 being the capital. $Q$ represents the modulus for the total number of ways to design the routes. The next $M$ lines each contain two distinct positive integers $a_i, b_i$ ($1 \le a_i, b_i \le N$), indicating that there is a highway connecting city $a_i$ and city $b_i$. The input data guarantees that each highway appears only once.

Output

The output file should contain two lines. The first line is an integer representing the minimum "inconvenience value". The second line is an integer representing the total number of different ways to design the routes to achieve the minimum "inconvenience value", modulo $Q$.

If any city cannot reach the capital, output -1 on both lines.

Examples

Input 1

5 4 100
1 2
4 5
1 3
4 1

Output 1

1
10

Note

The following are the 10 ways to design the routes in the example: (1) 4-5 (2) 1-4-5 (3) 4-5, 1-2 (4) 4-5, 1-3 (5) 4-5, 2-1-3 (6) 2-1-4-5 (7) 3-1-4-5 (8) 1-4 (9) 2-1-4 (10) 3-1-4

Constraints

For 20% of the data, $N, M \le 10$. For 50% of the data, $N, M \le 200$. For 60% of the data, $N, M \le 5000$. For 100% of the data, $1 \le N, M \le 100000$, $1 \le Q \le 120000000$.

Subtasks

Each test case is scored individually. For each test case, if the first line is incorrect, the test case receives zero points. Otherwise, if the second line is incorrect, the test case receives 40% of the points. If both questions are answered correctly, the test case receives 100% of the points.