挖矿

题目背景

ZY、ZHB、JGY、小罗翔 他们在我的世界中通过种小麦和养牛获得了足够的食物，他们意识到是时候向地底出发了。

题目描述

他们发现了 $n$ 个矿洞，以从 $1-n$ 的自然数标记，每个矿洞通过矿道最多连接 $q$ 个矿洞（形成一颗完全 $q$ 叉树,如下图)。他们分散在了不同的矿洞，因此他们想知道需要 两人交换物资时一共要经过几条矿道。

解释： 图中的圈为矿洞，直线为矿道，圈内的数字为矿洞的编号

输入格式

第一行是三个整数 $n,q,k$，表示矿洞个数、每个矿洞最多连接矿洞数、询问次数 。

第 $2 —— k+1$ 行每行两个整数 $x,y$，表示两人所处的矿洞

输出格式

$q$ 行，每行一个整数，表示询问的答案

样例 #1

8 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$。

找规律

数据非常的水，找到规律了以后时间复杂度可以不用考虑

本来想搞100个测试点的