Police Chase

题目描述

Kaaleppi 刚抢了银行，现在正前往海港。然而，警方想通过封闭城市中的一些街道来拦截他。 应封闭最少多少条街道以使得银行和海港之间不存在通路？

输入格式

第一行输入包含两个整数 n 和 m：路口数和街道数。路口编号为 1,2,$\dots$,n。银行位于路口 1，海港位于路口 n。 随后有 m 行描述街道。每行包含两个整数 a 和 b：表示在路口 a 和 b 之间有一条街道。所有街道为双向街道，并且任意两路口之间最多有一条街道。

输出格式

首先输出一个整数 k：应封闭的最少街道数。随后输出 k 行描述这些街道。你可以输出任意一个有效的解。

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

2
3 4
1 4

提示

$2 \le n \le 500$ $1 \le m \le 1000$ $1 \le a,b \le n$

标签: CSES1695|图论

来源

CSES1695|图论