UOJ Logo FLYIOI UOJ

FLYIOI

#39. flower

菊花图是从一个点向所有点连边的树。

菊花图

CZY不满足于这个简单的定义,于是他给了一个更高级的定义:

给定参数k,定义0阶菊花图为只有一个根节点的树,n阶(n1)菊花图为一个根节点下面有k个孩子,每个孩子都是n-1阶菊花图。

每个点的编号是这样的:从根开始,按照BFS的顺序从1开始对每个点编号。

LK造了一个1018阶菊花图,由于这个图太大了,计算两个点的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

数据范围

由于某些原因,本题采用捆绑测试。

设对于所有询问,u,vn

子任务0:1分,T=0

子任务1:29分,T10,n10000

子任务2:30分,T100000,n1000000

子任务3:40分,T100000,n1015

对于100%的数据,k为正整数且k100