题目描述

这座游乐园是一座真正的景观公园，园内各项游乐设施之间分布着大片森林。

一条巨大的树顶步道让游客能够探索树冠附近的奇特世界，并欣赏周围丘陵和湖泊的壮丽景色。

步道由若干木制平台组成。这些平台安装在树顶附近，离地高度各不相同，并由狭窄的木制通道连接。

每条通道恰好连接两个平台。一个平台连接的通道数量可以不同。在原来的步道结构中，忽略通道方向后，任意平台都可以到达任意其他平台。

为了提高安全标准，并缓解步道部分区域偶尔出现的拥堵问题，管理方决定把所有通道都改成严格的单向通道。

所有通道的方向确定后，人们发现出现了可达性问题：如果游客只能按照规定方向行走，并且不能离开步道，那么可能存在某个平台无法从另一个平台到达。

由于通道方向是管理方根据各种“美观与功能因素”确定的，不能修改任何已经确定的方向。

为了解决问题，管理方决定新建若干条单向通道。这些新通道将连接选定的平台，使得最终任意平台都能到达任意其他平台。

不会新建平台，步道的其他性质也保持不变。

管理方希望通过谨慎选择新通道的两个端点及其方向，使新建通道的数量最少。

请计算最少需要新建多少条通道，并输出一种最优建设方案。

输入格式

输入包含多组测试数据，直到文件结束。

每组测试数据的第一行包含两个整数 $N,M$：

其中：

• $N$ 表示平台数量；
• $M$ 表示当前已有的单向通道数量。

平台编号为：

接下来 $M$ 行，每行包含两个不同的整数 $u,v$，表示有一条从平台 $u$ 指向平台 $v$ 的单向通道。

输入中的所有有向边互不相同。

忽略方向后，原图保证连通。

最终的步道中，任意两个平台 $A$ 和 $B$ 之间至多存在两条通道：

• 一条方向为 $A\to B$；
• 一条方向为 $B\to A$。

因此，你不能输出一条已经存在的同方向通道，也不能重复输出同一条新通道。

输出格式

对于每组测试数据，首先输出一行一个整数 $R$，表示使整个有向图变为强连通图所需添加的最少通道数。

接下来输出 $R$ 行，每行包含两个整数 $u,v$，表示新建一条从平台 $u$ 指向平台 $v$ 的单向通道。

如果存在多种最优方案，输出任意一种即可。

样例

输入

5 6
1 2
2 3
3 1
2 4
4 5
5 4
4 3
2 1
3 1
4 1
6 5
1 4
1 5
1 6
2 4
3 4

一种合法输出

1
4 1
3
4 2
3 4
1 3
3
4 1
6 2
5 3

样例说明

输入中包含三组测试数据。

• 第一组只需要添加一条通道；
• 第二组需要添加三条通道；
• 第三组也需要添加三条通道。

由于答案不唯一，你的输出可以与样例不同，只要新增通道数量最少，并且添加后整个有向图强连通即可。