##### National Olympiad in Informatics, China, 2008

Country Z is located on a mystical peninsula far-away in the east.
During the dynasty when little Z reigned, roads were the major means of
transportation. There are total cities in country Z, and some cities
are connected by bidirectional roads. What's interesting is that the
longitudes of every city in country Z are unique, and that **each city
will be directly connected by a road to at most one city to its east**.
Country Z's capital city is its political, economic, and cultural center
of tourism, each day being visited by thousands of people from other
cities in country Z.

To make the traffic in country Z more smooth, little Z has decided to
establish some number of **courses**, rebuilding all the roads to
railroads.

We define a **course** to be a sequence of cities of length or
greater. **Each city occurs at most once in the sequence**, and adjacent
cities in the sequence are directly connected by roads (to be rebuilt as
railroads). Furthermore, **each city can only occur in at most one
course**. In other words, no two courses can have common sections.

Realistically speaking, it is obviously not possible to reconstruct all roads as railroads. Thus, it is still sometimes necessary to use coaches when traveling from certain cities to the capital, where each coach travels back and forth between adjacent cities directly connected by roads. Therefore, one may need to repeatedly switch back and forth between coaches and trains when traveling from some city to reach the capital.

We define a city's "inconvenience value" to be the number of times one must take a coach when traveling from it to the capital. The overall inconvenience value for country Z is the greatest inconvenience value amongst of all of its cities. Clearly, the capital's inconvenience value is . Little Z wants to know how to design the courses when reconstructing railroads to minimize the overall inconvenience value of country Z, as well as how many such ways to design the courses. Since the total number of possible designs may be very big, little Z only cares about the value of this astronomical number modulo .

Note: The course and the course are equivalent, and reversing any course will still result in the same course. Two designs are considered different if and only if one design contains a course that does not belong to the other design.

#### Input Specification

The first line contains three positive integers , , and , where
is the number of cities (numbered from to , city number is the
capital), is the total number of roads, and is the number by
which to modulo the total number of possible designs.

For the following lines, each line contains two different positive
integers and , indicating
that there is a road connected city and city . It is
guaranteed that each road only appears once in the input.

#### Output Specification

The output should contain two lines. The first line should contain one
integer, representing the minimum possible inconvenience value.

The second line should contain one integer, representing the number of
possible designs that will yield the minimum possible inconvenience
value, modulo .

If it is not possible to reach the capital from some city, then output
`-1`

on both lines.

#### Sample Input

```
5 4 100
1 2
4 5
1 3
4 1
```

#### Sample Output

```
1
10
```

#### Explanation

The following are the different designs that will yield the minimum inconvenience value of .

#### Constraints

For of the test cases, .

For of the test cases, .

For of the test cases, .

For of the test cases, , and .

#### Scoring

For each test case, if the first line of output is wrong then you will be given a score of zero. Otherwise if the second line is wrong, then you will score of the points for the test case. If both lines are correct, then you will score of the points for the test case.

## Comments