3364. 吉吉木坐地铁

单点时限: 2.0 sec

内存限制: 256 MB

A 国有许多城市。每个城市都只有一条地铁线路。这条地铁线路一定是一个双向环线,24 小时不间断运行。环线的意思是:地铁从一个车站出发,经过该城市其他所有车站恰好一次,再回到这个车站。由于地铁不能折返运行,所以为了达到环线的目标,每个城市都必须有 3 个以上车站。

A 国的所有的地铁站由国家总地铁公司统一管理。这些车站都有唯一的编号,比如说 A 国总共有 $n$ 个车站,这些车站的编号就是从 $1$ 到 $n$ 的。由于申请地铁站需要漫长的审批流程,单个城市的车站的编号不一定是连续的:有可能 1 号和 3 号车站都在上海,而 2 号车站就在杭州。地铁站的设立不会是没有意义的,一旦设立了一个地铁站,那么该城市的环线就必须经过它。

A 国的地铁线路图也很奇怪。他们只记录可以相互直达的车站。比如从曹杨路到金沙江路到中山公园,曹杨路到金沙江路就是相互直达的,会被记录下来,而曹杨路到中山公园就不会被记录。所以,对于一个有 $m$ 个地铁站的城市,由于只有一条环线,一定会有 $m$ 条记录。

A 国总地铁公司提供了一种服务,供你要查询从一个车站到另外一个车站,坐地铁最少需要经过几站。现在你要设计一个程序:对于每一个查询,回答这两个车站之间最少要经过几站。或者不可达。

注意,经过的站数不算起点站,也就是说从曹杨路到中山公园,是两站。

吉吉木:我实在编不下去了。

输入格式

输入第一行两个整数 $n,q$ $(3 \leq n \leq 10^5, 1 \leq q \leq 100)$。

接下来 $n$ 行,是一张全国的地铁线路图。每行两个整数 $s,t$ $(1 \leq s, t \leq n, s \neq t)$,表示 $s,t$ 车站相互直达。数据保证,同一组 $s,t$ 不会出现多次。

接下来 $q$ 行,每行两个整数 $u,v$ $(1 \leq u, v \leq n, u \neq v)$。表示询问。

数据保证每个城市至少有三个地铁站。

输出格式

对于每次询问,输出答案。如果 $u$ 和 $v$ 之间不可达,输出 $-1$。

样例

Input
7 4
6 5
1 2
5 4
3 1
4 7
7 6
3 2
1 3
1 4
5 7
5 4
Output
1
-1
2
1

64 人解决,76 人已尝试。

79 份提交通过,共有 305 份提交。

3.7 EMB 奖励。

创建: 7 年,1 月前.

修改: 7 年,1 月前.

最后提交: 8 月,3 周前.

来源: 2017.9.27 ACM 选拔赛

题目标签