UOJ Logo Universal Online Judge

UOJ

#175. 新年的网警

附件下载 统计

零点的钟声敲响,猴年终于到来啦~

在这新年的第一天,猴族首领猴腮雷打算来整治一下网络风气。这时,他听说在一个叫做 Universal OJ 用户群 的 QQ 群中有人在散播(开)谣言(车),于是他就派了一群网警把这个用户群里的人都抓了回来,试图找到谣言的源头。

这个用户群中有 $n$ 个人,这些人中存在 $m$ 对双向的直接认识关系,这个社交网络中任意两个人都是直接或者间接认识的。经过研究,谣言的散播以如下的方式进行:

  1. 首先在某个时刻 $T$,谣言的源头想出了一个谣言,于是他在时刻 $T + 1$ 把这个谣言讲给了所有和他直接认识的人听。
  2. 如果一个人在第 $i$ 个时刻第一次听到了这个谣言,他会在第 $i + 1$ 时刻时把这个谣言讲给所有和他直接认识的人听。

现在网警们问出来每一个人第一次听到这个谣言的时间,但是遗憾的是他们并不知道 $T$ 的具体数值。而且,谣言的发起者不会坐以待毙,他可以随便回答一个时间(当然也可以回答真实时间),而其他不是谣言的源头的人一定不会撒谎。(注意:网警知道谣言的发起者可以说谎

猴族首领猴腮雷根据网警们递交上来的口供,非常轻易的就推理出了谣言的源头是谁并把他绳之以法。但是他发现,有些情况下,根据口供还不能唯一确定嫌疑人(即嫌疑人可能有多个),于是他想要知道哪些人是“安全的谣言发起人”。

一个人是安全的谣言发起人,当且仅当他可以通过捏造口供使得猴腮雷无法唯一确定嫌疑人(具体可以看样例解释)。

输入格式

第一行一个正整数 $T$,表示数据组数。

对于每组数据,第一行包含两个正整数 $n$ 和 $m$。

接下来 $m$ 行每行两个整数 $u$ 和 $v$ 表示第 $u$ 个人和第 $v$ 个人认识。保证 $1 \leq u, v \leq n$ 且 $u \neq v$ 且任意两个人的认识关系至多被描述一遍。

输出格式

对于每组数据,第一行输出一个正整数,表示安全谣言发起人数目 $K$。

第二行输出 $K$ 个从小到大的正整数,表示这 $K$ 个发起人的编号。

样例一

input

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

output

2
1 2
0

3
1 2 3

explanation

对于第一组数据:

  1. 第一个人在时刻 $7000$ 时散布谣言,并撒谎他是在时刻 $7001$ 时听到的,这时他就安全了。
  2. 第二个人在时刻 $7000$ 时散布谣言,并撒谎他是在时刻 $7001$ 时听到的,这时他就安全了。

对于第三组数据:

  1. 第一个人在时刻 $998244352$ 时散布谣言,并撒谎他是在时刻 $998244353$ 时听到的,这时他就安全了。
  2. 第二个人在时刻 $998244352$ 时散布谣言,并撒谎他是在时刻 $998244353$ 时听到的,这时他就安全了。
  3. 第三个人在时刻 $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}$

下载

样例数据下载