#P7995. [2021年山东省队集训d5]有向图

    ID: 8008 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-深度优先搜索随机排列树上差分low-link

[2021年山东省队集训d5]有向图

题目描述

给定一个有向图,满足其中任意两个点可以互相到达。

对于图中的某一个点 uu,如果对于任意一个点 vv,在图中只存在一条从 uu 到 vv 的初级道路(即,不经过重复点的道路),那么我们就认为 uu 是有趣的。

特别地,给定的有向图中至少有 20%20\% 的节点是有趣的。

你的任务就是找出所有的有趣结点。

输入格式

输入包含多组数据。

第一行输入一个整数 tt,代表数据组数。

下面对于每组数据:

第一行包含两个整数 n,mn,m;

接下来 mm 行,每行包含两个整数 u,vu,v,代表一条从 uu 到 vv 的有向边。

数据保证不包含重边,且给出的图是符合要求的。

输出格式

对于每组数据,输出一行,按照编号从小到大的顺序输出每个有趣结点。

样例 #1

样例输入 #1

2
3 3
1 2
2 3
3 1
7 10
1 2
2 3
3 1
1 4
4 5
5 1
4 6
6 7
7 4
6 1

样例输出 #1

1 2 3
1 2 3 5

提示

对于 30%30\% 的测试点,n≤500,m≤2000n≤500,m≤2000;

对于全部测试点,1≤t≤2000,1≤n≤105,1≤m≤2⋅1051≤t≤2000,1≤n≤10^5,1≤m≤2⋅10^5,且所有数据的 n,mn,m 之和分别不超过 10510^5 和 2⋅1052⋅10^5。