#P5201. 强连通问题

    ID: 2268 传统题 2000ms 512MiB 尝试: 166 已通过: 49 难度: 4 上传者: 标签>难度分类普及+/提高-枚举与搜索广度优先搜索构造与建模图构造CF1600鸣谢Claris提供翻译及SPJ

强连通问题

[NEERC2017] Connections

给定一个n个点,m条边的强连通有向图。请保留其中恰好2n条边,使得它还是强连通的。

输入输出格式

输入格式

从标准输入读入。第一行一个正整数 TT,表示数据组数。

每组数据第一行包含两个正整数n,m(n>=4,m>2n),表示点数和边数。

接下来m行,每行两个正整数x,y(1<=x,y<=n,x!=y),表示一条x到y的单向边。

数据保证图强连通,且不存在重边

sum(n),sum(m)<=100000。

输出格式

对于每组数据,向标准输出写出 m−2nm-2n 行。

每行描述一条要被删除的边,和输入格式一样,有多解输出任意一组。

样例

样例输入

1
4 9
1 2
1 3
2 3
2 4
3 2
3 4
4 1
4 2
4 3

样例输出

1 3

样例说明

原图中虚线表示样例删除的边 1→31\to3;其余边仍使图强连通。

来源

鸣谢Claris提供翻译及SPJ