一种新型的无带宽限制无线通信技术刚刚经过测试，被证明是现有光纤通信网络的合适替代方案，后者正难以应对流量的增长。你负责决定新通信网络的布局。当前的通信网络由一组节点（用于路由消息）和光纤链路组成，每条链路连接两个不同的节点。对于每一对节点，至少存在一条（为了带宽考虑，可能有多条）沿光纤连接两者的路径。

新的通信网络将不再使用任何光纤。取而代之的是无线链路，每条链路连接两个节点。这些链路带宽无限但造价昂贵，因此决定尽可能少地建立这些链路以提供连通性；对于每一对节点，沿无线链路连接它们的路径必须有且仅有一条。此外，你发现每个节点在建造时都预设了特定的连接数。对于每个节点，如果它连接的链路数量与今天不同，则必须进行重组，而这是昂贵的。

你的任务是设计新网络，使其在每对节点之间恰好有一条路径，同时最小化连接数与原始网络不同的节点数量。图 K.1 展示了原始网络以及样例输入 1 的一种解决方案。

图 K.1：样例输入 1 的说明。

输入格式

输入的第一行包含两个整数 $n$ ($2 \le n \le 10^4$) 和 $m$ ($1 \le m \le 10^5$)，分别表示现有网络中的节点数和光纤链路数。节点编号从 $0$ 到 $n-1$。接下来的 $m$ 行，每行包含两个不同的整数 $a_i$ 和 $b_i$，表示第 $i$ 条光纤链路连接编号为 $a_i$ 和 $b_i$ 的节点。保证对于每一对节点，至少存在一条路径连接它们。任意一对节点之间可能有多条光纤链路连接。

输出格式

输出连接数需要改变的节点的最小数量。在下一行，以与输入相同的格式显示连接系统。即，显示一行包含节点数（与输入相同）和无线链路数，随后在后续行中描述这些链路。如果存在多种可能的布局，则任何有效的布局均可被接受。

样例

输入格式 1

7 11
0 1
0 2
0 5
0 6
1 3
2 4
1 2
1 2
1 5
2 6
5 6

输出格式 1

3
7 6
0 1
0 2
0 5
0 6
3 6
4 6

输入格式 2

4 3
0 1
2 1
2 3

输出格式 2

0
4 3
2 1
1 3
0 2