#P5201. 强连通问题
强连通问题
[NEERC2017] Connections
给定一个n个点,m条边的强连通有向图。请保留其中恰好2n条边,使得它还是强连通的。
输入输出格式
输入格式
从标准输入读入。第一行一个正整数 ,表示数据组数。
每组数据第一行包含两个正整数n,m(n>=4,m>2n),表示点数和边数。
接下来m行,每行两个正整数x,y(1<=x,y<=n,x!=y),表示一条x到y的单向边。
数据保证图强连通,且不存在重边
sum(n),sum(m)<=100000。
输出格式
对于每组数据,向标准输出写出 行。
每行描述一条要被删除的边,和输入格式一样,有多解输出任意一组。
样例
样例输入
1
4 9
1 2
1 3
2 3
2 4
3 2
3 4
4 1
4 2
4 3
样例输出
1 3
样例说明
原图中虚线表示样例删除的边 ;其余边仍使图强连通。

来源
鸣谢Claris提供翻译及SPJ