You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1695 题。

题目描述

Kaaleppi 刚刚抢劫了一家银行，现在正朝港口方向逃跑。然而，警察想通过封闭一些街道来阻止他。

问题是：为了确保银行和港口之间没有任何通路，至少需要关闭多少条街道？

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示交叉口的数量和街道的数量。交叉口编号为 $1,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

说明/提示

$2 \leq n \leq 500$；

$2 \leq m \leq 1000$；

$1 \leq a, b \leq n$。