1468. 罗莎莉亚的伐木工作

罗莎莉亚因为摸鱼太久被抓了起来。现在要在芭芭拉的监督下进行伐木工作,然后将砍来的木柴卖给旅行者。

因为旅行者建造的房子有点特殊,要求卖给TA的木柴要两个边连在一起。

所以罗莎莉亚请你帮帮她,找一颗树上最多能有多少对边,每对边至少共用一个端点。当找到一对边后,这对边不计入之后的统计。而且树上还可能有重边,但没有环。或者你可以认为这棵树是一个除了重边外无环的连通图。

输入

第一行有两个正整数 n,m ,分别代表点数和边数。点的编号为 1,2,3,...,n ,边的编号为 1,2,3,...,m ( 2 \leq n \leq 2 \times 10^5 ,{n-1} \leq m \leq 2 \times 10^5 )

接下来有 m 行。在这 m 行中的第 i 行,每行有两个数 u,v ,分别代表编号为 i 的边的两个端点的编号。

输出

先输出一行数字 x ,表示最多能找到多少对边。

然后输出 x 行,每行两个数,代表你找到的一对边的两个边的编号。

如果有多种方案,输出任意一种即可。

样例

标准输入 复制文本
5 6
1 4
2 3
4 1
2 1
4 5
1 2
标准输出 复制文本
3
5 1
2 4
3 6

来源

2021 软件学院 ACM 集训队筛选赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 28
通过 15