9505 - 删边

给定一个 n 个点 m 条边的简单无向连通图，点从 1 开始编号。你可以删掉任意条边，使得：

  • 删完后图不连通；
  • 删完后图中没有孤立点（即度数为 0 的点）。

构造删边方案或报告无解。如果有多种合法方案，你只需要输出任意一种。

输入

第一行两个整数 n,m。

接下来 m 行，每行两个整数，表示这条边的两个端点的编号。

输出

如果有解：

  • 第一行输出一个整数 k 表示你要删的边数；
  • 接下来输出 k 行，每行两个整数，表示这条边的两个端点的编号。

样例

输入

7 10
2 1
2 3
2 4
2 5
2 6
2 7
4 3
5 4
6 7
6 3

输出

5
2 3
2 4
2 5
2 6
2 7

提示

对于 100\% 的数据，2 \le n,m\le5\times10^5。

来源

ZHQOI

时间限制 2 秒
内存限制 128 MB
讨论 统计
上一题 下一题