採礦

問題背景

ZY、ZHB、JGY 和小羅翔通過在我的世界中種小麥和養牛獲得了足夠的食物，他們意識到是時候向地底出發了。

問題描述

他們發現了 $n$ 個礦洞，以從 $1-n$ 的自然數標記，每個礦洞通過礦道最多連接 $q$ 個礦洞（形成一顆完全 $q$ 叉樹，如下圖)。他們分散在不同的礦洞，因此他們想知道需要兩人交換物資時一共要經過幾條礦道。

解釋： 圖中的圈為礦洞，直線為礦道，圈內的數字為礦洞的編號

輸入格式

第一行是三個整數 $n,q,k$，表示礦洞個數、每個礦洞最多連接礦洞數、詢問次數 。

第 $2 —— k+1$ 行每行兩個整數 $x,y$，表示兩人所處的礦洞

輸出格式

$q$ 行，每行一個整數，表示詢問的答案

範例 #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

詢問一: 不需要經過礦道

詢問二：4->1->2->5 經過三條礦道

詢問三：1->4 經過一條礦道

提示

• 對於 $5\%$ 的數據，$1\le n,q\le 1\times10^2$，$1\le K\le 5$；
• 對於 $100\%$ 的數據，$1\le n,q\le 1\times 10^6$，$1\le K\le 1 \times 10^5$。

找規律

數據非常的水，找到規律了以後時間複雜度可以不用考慮。