코스 설계

국가 Z는 동쪽 끝의 신비로운 반도에 있다. 어린 Z가 다스리던 왕조 시절에는 도로가 주된 교통수단이었다. 국가 Z에는 $N$개의 도시가 있고, 일부 도시끼리는 양방향 도로로 연결되어 있다. 국가 Z의 모든 도시는 경도가 서로 다르며, 각 도시는 자신보다 동쪽에 있는 도시 중 최대 한 곳과만 도로로 직접 연결되어 있다. 수도는 정치, 경제, 문화, 관광의 중심지이며, 매일 다른 도시에서 수천 명이 찾아온다.

국가 Z의 교통을 원활하게 하려고 어린 Z는 여러 개의 코스를 만들어 모든 도로를 철도로 바꾸기로 했다.

코스는 길이가 1 이상인 도시의 나열이다. 나열에 같은 도시는 한 번만 등장하고, 나열에서 인접한 도시는 도로로 직접 연결되어 있다(이 도로는 철도로 바뀐다). 각 도시는 최대 하나의 코스에만 속하므로, 두 코스가 도시를 공유하지 않는다.

모든 도로를 철도로 바꾸는 것은 현실적으로 불가능하므로, 일부 구간에서는 여전히 버스를 이용해야 한다. 버스는 도로로 직접 연결된 인접 도시 사이를 오가며 운행한다. 따라서 어떤 도시에서 수도로 갈 때 버스와 기차를 여러 번 번갈아 타야 할 수도 있다.

도시의 불편도는 그 도시에서 수도까지 갈 때 버스를 타야 하는 횟수이다. 국가 Z의 전체 불편도는 모든 도시의 불편도 중 최댓값이다. 수도의 불편도는 0이다. 어린 Z는 전체 불편도가 최소가 되도록 코스를 설계하는 방법과, 그런 설계의 개수를 알고 싶어 한다. 설계의 개수는 매우 클 수 있으므로 $Q$로 나눈 나머지를 출력한다.

코스 1-2-3과 코스 3-2-1은 같은 코스이며, 코스를 뒤집어도 같은 코스이다. 두 설계가 다른 것은, 한쪽에 다른 쪽에는 없는 코스가 포함된 경우에만 해당한다.

첫 줄에 양의 정수 $N$, $M$, $Q$가 주어진다. $N$은 도시의 수이며 도시는 1부터 $N$까지 번호가 매겨지고, 도시 1이 수도이다. $M$은 도로의 수이고, $Q$는 나눌 수이다. 이어지는 $M$개의 줄에는 서로 다른 양의 정수 $a_i$와 $b_i$($1 \le a_i, b_i \le N$)가 주어지며, 이는 도시 $a_i$와 도시 $b_i$가 도로로 연결되어 있음을 뜻한다. 같은 도로는 입력에 한 번만 나온다.

출력은 두 줄이다. 첫 줄에는 가능한 전체 불편도의 최솟값을 출력한다. 둘째 줄에는 그 최솟값을 달성하는 설계의 개수를 $Q$로 나눈 나머지를 출력한다. 어떤 도시에서 수도에 도달할 수 없으면 두 줄 모두 $-1$을 출력한다.

$1 \le N, M \le 100000$, $1 \le Q \le 120000000$.