32161번 - 축지법

문제

A씨는 출근 시간 심각한 교통 체증에 골머리를 앓고 있다. A씨의 활동 범위에는 1ドル$번부터 $N$번까지 $N$개의 지점과 서로 다른 두 지점을 잇는 $M$개의 양방향 도로가 있다. 각 도로를 지나는 데는 1ドル$분이 걸린다.

훌륭한 도술가 A씨는 축지법을 써서 각 지점에서 원하는 지점으로 1ドル$분 만에 이동할 수 있다. 하지만 현재 지점에서 0ドル$개 이상의 도로를 거쳐 도착할 수 있는 지점의 경우, 축지법으로 즉시 이동하는 것을 새치기로 간주하여 도술가 윤리 강령에서 엄격히 금하고 있다.

출발점과 도착점이 $Q$쌍 주어질 때, 각 쌍마다 출발점에서 도착점으로 이동하는 데 걸리는 최소 시간을 구해 보자.

입력

첫 번째 줄에 지점의 수 $N$과 도로의 수 $M,ドル 질문의 수 $Q$가 공백으로 구분되어 주어진다. (2ドル \le N \le 10^9$; 1ドル \le M \le 2,000円$; 1ドル \le Q \le 5 \times 10^5$)

다음 $M$개의 줄에 걸쳐 한 줄에 하나씩 각 도로 양 끝 지점의 번호 $u,ドル $v$가 공백으로 구분되어 주어진다. (1ドル \le u \lt v \le N$) 어떤 두 도로도 양 끝 지점이 모두 같지 않다.

다음 $Q$개의 줄에 걸쳐 한 줄에 하나씩 출발점의 번호 $s$와 도착점의 번호 $e$가 공백으로 구분되어 주어진다. (1ドル \le s, e \le N$)

출력

각 쌍마다 출발점에서 도착점으로 이동하는 데 걸리는 최소 시간을 한 줄에 하나씩 $Q$줄에 걸쳐 출력한다.

제한

힌트