| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 119 | 60 | 53 | 54.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$을 출력함에 유의하라.
5 5 1 2 1 3 1 5 2 5 3 4
0 1 2 1 3 2 1 1 2 1
School > 경기과학고등학교 > 나는코더다 송년대회 > 나는코더다 2025 송년대회 J번