/ Randle / 题库 /

三向城T1

三向城T1

题目描述
三向城是一个巨大的城市,之所以叫这个名字,是因为城市中遍布着数不尽的三岔路口。(来自取名力为0的出题人)
具体来说,城中有无穷多个路口,每个路口有唯一的一个正整数标号。除了1号路口外,每个路口都连出正好3条道路通向另外3个路口:编号为x(x>1)的路口连出3条道路通向编号为x*2,x*2+1和x/2(向下取整)的3个路口。1号路口只连出两条道路,分别连向2号和3号路口。
所有道路都是可以双向通行的,并且长度都为1。现在,有n个问题:从路口x到路口y的最短路长度是多少?

输入格式
第一行包含一个整数n,表示询问数量;
接下来n行,每行包含两个正整数x, y,表示询问从路口x到路口y的最短路长度。

输出格式
输出n行,每行包含一个整数,表示对每次询问的回答。如果对于某个询问不存在从x到y的路径,则输出-1。

样例输入

3
5 7
2 4
1 1

样例输出

4
1
0

样例解释
5号路口到7号路口的路径为:5->2->1->3->7,长度为4;
2号路口到4号路口的路径为:2->4,长度为1;
1号路口到本身的路径长度为0;

数据范围
对30%的数据,x,y≤20;
对60%的数据,x,y≤105,n≤10;
对100%的数据,x,y≤109,n≤104。

信息

难度
6
分类
(无)
标签
(无)
递交数
30
已通过
11
通过率
37%
被复制
1
上传者