HZNUOJ

小Q的最短路

Tags:
Time Limit:  2 s      Memory Limit:   512 MB
Submission:349     AC:99     Score:93.28

Description

小Q有一张无向图$G = <V, E>$,这个图一共有$n$个点,并且对于每一对点$(i, j)$来说,都有一条边$e(i, j) = gcd(i, j)$。
它想询问您$q$次,每次询问给出一点对$(s, t)$,它想知道$s \rightarrow t$的最短路径的距离。

图:
图(Graph)是由两个集合构成,一个是非空但是有限的顶点集合$V$,另一个是描述结合间的关系边的集合$E$,因此图可以表示为$G=<V, E>$.每条边是一对顶点$(v,w)$且 $v,w \in V$.通常$|V|$和$|E|$表示顶点个数和边的数量。值得注意的是图中顶点一定不能为空,而边可以为空。

无向图:
无向图是指图中的边没有方向性即边$(v,w)$与边$(w,v)$是同一条边。用圆括号"( )"来表示无向边。

Input

单组数据评测。
第一行两个正整数$n, q(2 \leq n, q \leq 10^5)$,表示图中有$n$个点以及$q$次询问。
接下来$q$行,每行两个正整数$s_i, t_i(1 \leq s_i, t_i \leq n, s_i \neq t_i)$,表示它想知道$s_i \rightarrow t_i$的最短路径的距离。

Output

输出包含$q$行,每行一个正整数表示$s_i \rightarrow t_i$的最短路径的距离。

Samples

input
5 3 1 2 2 3 3 4
output
1 1 1

Author

PAN, Lyuzhi