三向城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
- 上传者