CSES1695 警察追击
#CS1695. 警察追击
警察追击
题目背景
翻译自 CSES-1695 题。
题目描述
Kaaleppi 刚刚抢劫了一家银行，现在正朝港口方向逃跑。然而，警察想通过封闭一些街道来阻止他。
问题是：为了确保银行和港口之间没有任何通路，至少需要关闭多少条街道？
输入格式
第一行包含两个整数 n 和 m：分别表示交叉口的数量和街道的数量。交叉口编号为 1,2,…,n1,2,…,n1,2,…,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
说明/提示