3364. 吉吉木坐地铁

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

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

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

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

输入格式

输入第一行两个整数 n,q (3n105,1q100)

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

接下来 q 行,每行两个整数 u,v (1u,vn,uv)。表示询问。

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

输出格式

对于每次询问,输出答案。如果 uv 之间不可达,输出 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

73 人解决,117 人已尝试。

91 份提交通过,共有 406 份提交。

4.5 EMB 奖励。

创建: 7 年,7 月前.

修改: 7 年,7 月前.

最后提交: 19 小时前.

来源: 2017.9.27 ACM 选拔赛

题目标签