← 返回题目列表

Codeforces · 2068/E

E. 波尔图对阵。本菲卡

中文机器翻译题面 查看原题

波尔图足球俱乐部和本菲卡足球俱乐部是葡萄牙最大的两支足球队。自然,当两人交手的时候,很多人从全国各地专程赶来观看比赛。其中包括本菲卡球迷俱乐部,他们将从里斯本前往波尔图观看即将到来的比赛。为了避免他们和波尔图球迷俱乐部之间的紧张关系,国家警察希望尽可能推迟他们抵达波尔图的时间。

葡萄牙的道路网络可以建模为一个简单、无向、未加权的连通图,具有 $$$n$$$ 个顶点和 $$$m$$$ 个边,其中顶点代表城镇,边代表道路。顶点$$$1$$$对应里斯本,即球迷俱乐部的起始顶点,顶点$$$n$$$对应波尔图,即球迷俱乐部的目的地顶点。支持者俱乐部希望尽量减少到达波尔图的道路数量。

警察正在仔细跟踪球迷俱乐部,所以他们总是知道他们在哪里。为了延迟他们的到来,警察可以在任何时候选择一条道路并封锁它,只要球迷俱乐部目前没有经过它。他们只能这样做一次,一旦他们这样做了,路就永远被堵住了。一旦警察封锁了一条道路,球迷俱乐部就会立即得知这条路被封锁了,他们可以随意改变路线。此外,球迷俱乐部知道警方正在计划封锁一些道路,并可以相应地规划他们的路线。

假设球迷俱乐部和警察总是做出最优选择,确定球迷俱乐部从里斯本到波尔图需要经过的最少道路数。如果警察可以阻止球迷俱乐部到达波尔图,则输出$$$-1$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 200\,000$$$, $$$n - 1 \leq m \leq \min\{n(n - 1)/2, 200\,000\}$$$) — 城镇数量和道路网络中的道路数量葡萄牙。

接下来的 $$$m$$$ 行包含两个整数 $$$s_i$$$ 和 $$$t_i$$$ ($$$1 \leq s_i, t_i \leq n$$$) — 由第 $$$i$$$ 条路连接的两个城镇。

保证路网连通,每条道路连接两个不同的城镇,并且不存在重复的道路。

输出

打印球迷俱乐部从里斯本到波尔图所需经过的最少道路数量。

示例

输入
复制

5 5
1 2
1 3
2 5
3 4
4 5

输出
复制

5

输入
复制

11 12
1 2
2 3
3 4
4 5
5 11
3 6
6 7
7 11
1 8
8 9
9 10
10 11

输出
复制

9

输入
复制

8 10
1 2
2 3
3 4
3 8
4 8
1 5
5 6
6 7
6 8
7 8

输出
复制

5

注意

在 第一个样本,路网如下图表示:

请注意,警察的最佳策略是等到支持者俱乐部位于与目的地相邻的顶点(即顶点 $$$5$$$),然后封锁将该顶点连接到目的地的边。支持者俱乐部的最佳策略是沿着上面的路径(从 $$$1$$$ 到 $$$2$$$),然后在看到 $$$2$$$ 和 $$$5$$$ 之间的边缘被阻挡后,他们会沿着 $$$2$$$ 回到 $$$1$$$,然后沿着下面的路径($$$1$$$ 到 $$$3$$$ 到 $$$4$$$ 到$$$5$$$)。本例中经过的道路数量为 $$$5$$$。

在 第二个样本,路网如下图表示:

这里有多种策略,但可以验证警察和球迷俱乐部的最佳策略是沿着上面的路径($$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$),然后警察封锁边缘 $$$5$$$ 到 $$$11$$$,因此球迷俱乐部沿着 $$$5 \rightarrow 4 \rightarrow 绕行3 \右箭头 6 \右箭头 7 \右箭头 11$$$。该策略遍历的道路总数为$$$9$$$。

在 第三个样本,路网如下图表示:

警察的最佳策略是,如果支持者俱乐部到达顶点 $$$2$$$,则阻止边 $$$2$$$ 到 $$$3$$$,或者如果支持者俱乐部到达顶点 $$$5$$$,则阻止边 $$$5$$$ 到 $$$6$$$。本例中的最佳路径是 $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 6 \rightarrow 8$$$。本例中经过的道路总数为 $$$5$$$。