채굴

문제 배경

ZY, ZHB, JGY 및 Little Luo Xiang은 내 세계에서 밀을 심고 소를 키우며 충분한 식량을 얻었습니다. 그들은 이제 지하 여행을 시작할 때입니다.

문제 설명

그들은 $n$개의 광산을 발견했습니다. 1부터 $n$까지의 자연수로 표시되며, 각 광산은 최대 $q$개의 다른 광산과 연결될 수 있습니다 (아래 그림과 같이 완전 $q$진 트리를 형성합니다). 그들은 서로 다른 광산에 흩어져 있으며 자원을 교환할 때 몇 개의 광산을 지나가야 하는지 알고 싶습니다.

설명: 그림에서 원은 광산을 나타내며 직선은 터널을 나타내며 원 내부의 숫자는 광산의 번호입니다.

입력 형식

첫 번째 줄에 $n, q, k$를 나타내는 세 개의 정수가 있으며, 각각 광산의 수, 각 광산이 연결할 수 있는 광산의 최대 수 및 질의 수를 나타냅니다.

다음 $k$줄 (2번째부터 $k+1$번째 줄)은 각각 두 개의 정수 $x, y$를 포함하며, 두 명의 사람이 위치한 광산을 나타냅니다.

출력 형식

$k$개의 줄로 구성되며, 각각 질의에 대한 답을 나타냅니다.

예제 #1

10 3 3
1 1
4 5
1 4

0
3
1

10 5 1
9 6

3

10 1 3
4 2
2 7
10 3

2
5
7

예제 설명

예제 1

질의 1: 광산을 통과할 필요가 없습니다.

질의 2: 4 -> 1 -> 2 -> 5, 세 개의 광산을 통과합니다.

질의 3: 1 -> 4, 한 개의 광산을 통과합니다.

힌트

• 데이터의 5%에 대해서는 $n, q \le 10^2$, $k \le 5$입니다.
• 데이터의 100%에 대해서는 $n, q \le 10^6$, $k \le 10^5$입니다.

패턴 찾기

데이터는 매우 자유롭습니다. 패턴을 찾으면 시간 복잡도를 걱정할 필요가 없습니다.