3494. 道路死角

【题目描述】

小明是家乡的一名基层公务员，由于家乡道路建设的不规范，导致有很多道路死角，为车辆通行带来 很多麻烦。当地公路管理部门经过征求群众意见和开会决定改进道路标识的位置，特别是存在道路死 角的路。公路部门为小明提供了交通道路图，需要小明决定在哪条道路上增加标识用以标记死角，他 们希望小明使用尽量少的死角标识。道路地图是由双向街道连接的位置组成的集合

下面定义了关于道路死角的规则：

1、对于一条道路S，存在位置x和另一个位置相通；如果从x位置进入道路S，假如不掉头就不能回到x 位置，则道路S的x入口就是道路死角。(掉头是指立即朝相反的方向180度转弯)。

2、为了节省成本，小明决定满足下面规则的道路口不安装道路死角标识：假如一条道路S的x位置处 带有死角标识和一条道路T的y位置处带有死角标识；如果从x位置进入道路S后，可以在不通过U形转 弯的情况下进入y位置处并进入道路T，那么就取消T道路y位置处的死角标识

【输入格式】

输入的第一行包含两个整数n和m，其中n（1≤n≤5*10^5）是位置数，m（0≤m≤5*10^5）是道路 数。 接下来的m行中的每行包含两个整数v和w（1≤v<w≤n），表示存在一条双向街道，将位置v和w连接 起来。 输入中的所有位置对都是不同的

【输出格式】

在第一行，输出k，即已安装的死角标识的数量。 

在接下来的k行中，输出两个整数v和w，表示在连接位置v和w的道路的v位置处应安装一个死角标识。 描述道路死角标识的行必须按位置v的升序排序(输出:v w)；如果在v处不存在死角标记，w处存在死角 标记，按照位置w的升序排序(输出：w v)。

【样例输入】

样例输入 1 
6 5  
1 2  
1 3 
2 3   
4 5  
5 6 
样例输入 2 
8 8  
1 2 
1 3
2 3  
3 4  
1 5  
1 6   
6 7  
6 8

【样例输出】

样例输出 1 
2  
4 5  
6 5 
样例输出 2 
3  
1 5  
1 6  
3 4
样例1，2图示  

【数据范围】

对于10%的测试点，1≤n≤500，0≤m≤5*10^5

对于30%的测试点，1≤n≤50000，0≤m≤5*10^5 

对于100%的测试点，1≤n≤5*10^5，0≤m≤5*10^5