菊花图是从一个点向所有点连边的树。
CZY不满足于这个简单的定义,于是他给了一个更高级的定义:
给定参数k,定义0阶菊花图为只有一个根节点的树,n阶()菊花图为一个根节点下面有k个孩子,每个孩子都是n-1阶菊花图。
每个点的编号是这样的:从根开始,按照BFS的顺序从1开始对每个点编号。
LK造了一个阶菊花图,由于这个图太大了,计算两个点的LCA成了一件难事,现在他给了一些询问,每组询问形如u,v表示计算u和v的LCA。
由于图太大了,LK一个询问都不会,于是他把这些询问丢给了你,请你帮他解决,并且承诺如果你帮他算出来就给你一定的分数作为奖励。
输入格式
第一行两个数T,k,T表示有T组询问,菊花图的参数为k。
接下来T行,每行两个数u,v表示计算u和v的LCA。
输出格式
T行,每行一个数lca表示u和v的LCA。
样例输入输出
样例输入
3 2 1 4 4 5 3 8
样例输出
1 2 1
数据范围
由于某些原因,本题采用捆绑测试。
设对于所有询问,。
子任务0:1分,。
子任务1:29分,
子任务2:30分,。
子任务3:40分,。
对于的数据,k为正整数且。