Description

Country Z lies on a distant and magical eastern peninsula. During the reign of Xiao Z, highways became the main mode of transportation. There are $N$ cities in Country Z, and some pairs of cities are connected by bidirectional highways. Remarkably, each city has a unique longitude, and each city is directly connected by highway to at most one city located to its east. The capital is the political, economic, cultural, and tourism center of Country Z, and every day thousands of people flow into the capital from other cities.

To make transportation more convenient and efficient, Xiao Z decides to designate several planned routes in the highway system and rebuild all highways on these routes into railways.

We define each planned route as a city sequence of length strictly greater than $1$, where each city appears at most once in the sequence, and each pair of adjacent cities in the sequence is directly connected by a highway (to be rebuilt into railway). Moreover, each city can appear in at most one planned route, i.e., any two planned routes must be vertex-disjoint.

Of course, in general it is impossible to rebuild all highways into railways, so traveling from some cities to the capital still requires taking long-distance buses. Long-distance buses only run between adjacent cities that are connected by a highway, so starting from a given city, one may need to alternate between taking buses and trains to reach the capital.

We define the “inconvenience value” of a city as the number of times one must take a long-distance bus to reach the capital from that city. The “inconvenience value” of the transportation system is the maximum inconvenience value over all cities. Clearly, the capital’s inconvenience value is $0$. Xiao Z wants to know how to choose planned routes to minimize the system’s inconvenience value, and how many different choices of planned routes achieve this minimum. Since the total number of plans may be huge, Xiao Z only cares about this astronomical number modulo $Q$.

Note: A planned route $1-2-3$ is equivalent to $3-2-1$, i.e., reversing a planned route is considered the same. Two plans are different if and only if there exists a planned route that appears in one plan but not in the other.

Input Format

The first line contains three positive integers $N, M, Q$, where $N$ is the number of cities, $M$ is the number of highways, and the cities are numbered from $1$ to $N$, with city $1$ being the capital. $Q$ is the modulus mentioned above for the number of route-design methods.

Each of the next $M$ lines contains two distinct 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 guarantees that each highway appears exactly once.

Output Format

Output two lines.

The first line contains one integer: the minimal “inconvenience value.”

The second line contains one integer: the number of different route-design methods that achieve the minimal “inconvenience value,” modulo $Q$.

If some city cannot reach the capital, output two lines, each containing $-1$.

5 4 100 
1 2 
4 5 
1 3 
4 1

1 
10

Hint

For $20\%$ of the testdata, $1 \le N, M \le 10$.

For $50\%$ of the testdata, $1 \le N, M \le 200$.

For $60\%$ of the testdata, $1 \le N, M \le 5000$.

For $100\%$ of the testdata, $1 \le N, M \le 10^5$, $1 \le Q \le 1.2 \times 10^8$.

Translated by ChatGPT 5