시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB119605354.082%

문제

움직이지 않고 여행하는 법을 알고 있는가?

$N$개의 나라가 있고, 각 나라에는 $1$부터 $N$까지의 번호가 붙어 있다. 당신은 순간 이동을 할 수 있어, $1$번 나라에서 시작해서 여러 번의 순간 이동을 통해 다른 나라로 여행하려고 한다.

당신은 순간 이동을 하기 때문에 어느 곳이나 갈 수 있다! 다만 $M$개의 쌍 $(u_i,\, v_i)$에 대해 $u_i$번 나라와 $v_i$번 나라 사이의 순간 이동이 양쪽 방향 모두 금지되어 있다. 이외의 순간 이동은 모두 허용된다.

순간 이동은 비싸기 때문에, 당신은 $1$번 나라에서 시작하여 $i$번 나라까지 최소한의 순간 이동으로 여행하려고 한다. 모든 $i$에 대해 순간 이동의 최소 횟수와, 최소 횟수로 여행하는 방법의 수를 구하여라.

입력

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($2 \leq N \leq 200\,000$; $0 \leq M \leq 500 \, 000$)

두 번째 줄부터 $M$개의 줄에 걸쳐 $i$번째 줄에는 $(u_i, v_i)$가 주어진다.

같은 쌍이 여러 번 주어지지 않음이 보장된다. 단, $(u_i, v_i)$와 $(v_i, u_i)$는 같은 쌍으로 간주한다.

$1$번 나라에서 시작하여 여러 번의 순간 이동을 통해 모든 나라에 도달할 수 있음이 보장된다.

출력

총 $N$개의 줄에 걸쳐 $i$번째 줄에는 $1$번 나라에서 시작하여 $i$번 나라까지 여행하기 위한 순간 이동의 최소 횟수와, 최소 횟수의 순간 이동으로 여행하는 방법의 수를 $998\, 244\, 353$으로 나눈 나머지를 공백으로 구분하여 출력하라.

아무것도 하지 않아도 $1$번 나라까지 여행할 수 있으므로, 첫 번째 줄은 항상 $0 \, 1$을 출력함에 유의하라.

예제 입력 1

5 5
1 2
1 3
1 5
2 5
3 4

예제 출력 1

0 1
2 1
3 2
1 1
2 1