题目描述

运动有益身心健康，某校希望举行一场户外耐力赛跑，于是精心策划了一条路线，在这条路线上，有 $n$ 个中转站，编号为 $1$ 到 $n$ ， $m$ 条跑道。但是校方希望学生在赛跑的途中同时也能欣赏到不同的户外风景，于是希望拆除一些跑道，让一些中转站不在环线上，使得学生不用走回头路。考虑到学生跑到后半段时基本没有精力看风景，于是校方决定，只让编号小于等于 $k$ 的中转站不在任意一个环线上，学校找到你来策划，问最少需要拆除多少条跑道，才能做到上述要求，并且给出具体拆除方案。

输入格式

第一行输入三个整数 $n$、$m$、$k$ 。

接下来 $m$ 行，每行输入两个整数 $u$，$v$，表示一条由 $u$ 到 $v$ 的双向边，每一对点之间至多只有一条边。

输出格式

第一行输出一个整数 $k$，表示最少的拆除跑道数量；

接下来 $k$ 行，每行输出两个正整数 $a,b$，表示删除编号 $a,b$ 中转站之间的跑道，先输出编号小的，再输出编号大的，如果有多种拆除顺序，输出任意一种即可。

样例 #1

样例输入 #1

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

样例输出 #1

3
2 3
5 9
3 5

数据范围

对于 $40\%$ 的数据： $n \le 1000,m \le 5000$ 。

对于 $100\%$ 的数据： $1 \le n \le 1\ 000\ 000,0 \le m \le 2\ 000\ 000,1 \le k \le n, 1 \le u \lt v \le n$ 。