P8046 [COCI 2015/2016 #4] CHEWBACCA

**本套赛题 T3 为 [P8053](https://www.luogu.com.cn/problem/P8053)。**

一棵 $n$ 个节点的 $k$ 级树是按照如下方式构造出来的： - 首先，新建根节点，并将其编号为 $1$。 - 随后重复如下步骤直至节点总数恰好为 $n$： - 设上一个新增节点的编号为 $x$。 - 在上一层中从左往右找到第一个儿子个数 $

第一行输入三个整数 $n,k,q$，分别表示树的节点数、级数和询问次数。 随后 $q$ 行，每行输入两个整数 $x,y$，表示本次询问的两个节点。

输出 $q$ 行，每行一个整数，表示节点 $x$ 到节点 $y$ 的最短路径长度。

**【样例 1 解释】** 下图是样例 1 中构造出来的树：  不难发现，对于第 $1$、$2$ 次询问，由于节点 $2$ 是节点 $1$ 的儿子节点，因此这两个点之间的最短路径长度恰好为 $1$。而对于第 $3$ 次询问，一条最短路径是 $4\rightarrow 2\rightarrow 1\rightarrow 3\rightarrow 7$。因此其最短路径长度为 $4$。 **【样例 2 解释】** 样例 2 构造出来的树见『题目描述』部分。 **【数据范围】** 对于 $20\%$ 的数据，保证 $1\leqslant n,q\leqslant 1000$。 对于 $50\%$ 的数据，保证 $1\leqslant n\leqslant 10^5$。 对于所有数据，$1\leqslant n\leqslant 10^{15}$，$1\leqslant k\leqslant 1000$，$1\leqslant q\leqslant 10^5$。 **【题目来源】** 本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T4 CHEWBACCA_**，按照原题数据配置，满分 $120$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。