uoj#P175. 新年的网警
新年的网警
零点的钟声敲响,猴年终于到来啦~
在这新年的第一天,猴族首领猴腮雷打算来整治一下网络风气。这时,他听说在一个叫做 Universal OJ 用户群 的 QQ 群中有人在散播(开)谣言(车),于是他就派了一群网警把这个用户群里的人都抓了回来,试图找到谣言的源头。
这个用户群中有 $n$ 个人,这些人中存在 $m$ 对双向的直接认识关系,这个社交网络中任意两个人都是直接或者间接认识的。经过研究,谣言的散播以如下的方式进行:
- 首先在某个时刻 $T$,谣言的源头想出了一个谣言,于是他在时刻 $T + 1$ 把这个谣言讲给了所有和他直接认识的人听。
- 如果一个人在第 $i$ 个时刻第一次听到了这个谣言,他会在第 $i + 1$ 时刻时把这个谣言讲给所有和他直接认识的人听。
现在网警们问出来每一个人第一次听到这个谣言的时间,但是遗憾的是他们并不知道 $T$ 的具体数值。而且,谣言的发起者不会坐以待毙,他可以随便回答一个时间(当然也可以回答真实时间),而其他不是谣言的源头的人一定不会撒谎。(注意:网警知道谣言的发起者可以说谎)
猴族首领猴腮雷根据网警们递交上来的口供,非常轻易的就推理出了谣言的源头是谁并把他绳之以法。但是他发现,有些情况下,根据口供还不能唯一确定嫌疑人(即嫌疑人可能有多个),于是他想要知道哪些人是“安全的谣言发起人”。
一个人是安全的谣言发起人,当且仅当他可以通过捏造口供使得猴腮雷无法唯一确定嫌疑人(具体可以看样例解释)。
输入格式
第一行一个正整数 $T$,表示数据组数。
对于每组数据,第一行包含两个正整数 $n$ 和 $m$。
接下来 $m$ 行每行两个整数 $u$ 和 $v$ 表示第 $u$ 个人和第 $v$ 个人认识。保证 $1 \leq u, v \leq n$ 且 $u \neq v$ 且任意两个人的认识关系至多被描述一遍。
输出格式
对于每组数据,第一行输出一个正整数,表示安全谣言发起人数目 $K$。
第二行输出 $K$ 个从小到大的正整数,表示这 $K$ 个发起人的编号。
3
2 1
1 2
5 5
1 2
2 3
3 4
4 5
5 1
3 3
1 2
2 3
3 1
2
1 2
0
3
1 2 3
对于第一组数据:
- 第一个人在时刻 $7000$ 时散布谣言,并撒谎他是在时刻 $7001$ 时听到的,这时他就安全了。
- 第二个人在时刻 $7000$ 时散布谣言,并撒谎他是在时刻 $7001$ 时听到的,这时他就安全了。
对于第三组数据:
- 第一个人在时刻 $998244352$ 时散布谣言,并撒谎他是在时刻 $998244353$ 时听到的,这时他就安全了。
- 第二个人在时刻 $998244352$ 时散布谣言,并撒谎他是在时刻 $998244353$ 时听到的,这时他就安全了。
- 第三个人在时刻 $998244352$ 时散布谣言,并撒谎他是在时刻 $998244353$ 时听到的,这时他就安全了。
样例二
见样例数据下载。
限制与约定
测试点编号 | $n$ 的规模 | $m$ 的规模 |
---|---|---|
1 | $n \leq 200$ | $m \leq 2 \times 10^5$ |
2 | ||
3 | ||
4 | $n \leq 2000$ | |
5 | ||
6 | ||
7 | $n \leq 100000$ | |
8 | ||
9 | ||
10 |
对于所有数据,保证 $1 \leq T \leq 5$,$n \geq 2$。
时间限制:$1\texttt{s}$
空间限制:$256\texttt{MB}$