UOJ Logo LFYZ Online Judge

LFYZOJ

#205. 三向城

统计

问题描述

三向城是一个巨大的城市,之所以叫这个名字,是因为城市中遍布着数不尽的三岔路口。具体来说,城中有无穷多个路口,每个路口有唯一的一个正整数标号。除了 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。

样例一

input

3
5 7
2 4
1 1

output

4
1
0

解释

5 号路口到 7 号路口的路径为:5->2->1->3->7,长度为 4;

2 号路口到 4 号路口的路径为:2->4,长度为 1;

1 号路口到本身的路径长度为 0;

数据范围与约定

时间限制: $1\mathrm{s}$

内存限制: $128\mathrm{MB}$

对 $30\%$的数据,$x,y\leq 20$;

对 $60\%$的数据,$x,y \leq 10^5,n \leq 10$;

对 $100\%$的数据,$x,y \leq 10^9,n \leq 10^4$。