← 返回题目列表

Codeforces · 1368/E

E. 滑雪事故

中文机器翻译题面 查看原题

亚瑟在山上拥有一个滑雪胜地。山上有$$$n$$$着陆点,从山顶到山脚编号为$$$1$$$至$$$n$$$。这些景点与单向滑雪道相连。所有轨道都通向山脚,因此轨道不形成有向循环。每个地点最多有两条轨道离开,但许多轨道可能会进入同一个地点。

如果存在从起始点到结束点的一系列轨迹,则滑雪者可以从一个点开始滑雪并在另一个点停止。不幸的是,最近发生了很多事故,因为滑雪场的结构允许滑雪者通过危险的路径,达到高速并危及自己和其他顾客。在这里,如果一条路径至少由两条轨道组成,则该路径被称为危险路径。

亚瑟希望通过关闭一些景点以确保度假村内没有危险路径来保护他的顾客。当某个地点关闭时,进入和离开该地点的所有轨道都将变得不可用。

正式来说,关闭一些景点后,不应该有一条由两条或更多轨道组成的路径。

Arthur 不想关闭太多地点。他会很高兴找到任何方法来关闭最多 $$$\frac{4}{7}n$$$ 点,以便剩余部分是安全的。帮助他找到任何合适的方法来做到这一点。

输入

第一行包含一个正整数 $$$T$$$ — 测试用例的数量。 $$$T$$$ 测试用例描述如下。

每个描述的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 分别是着陆点和轨道的数量。

以下 $$$m$$$ 行描述了轨道。每行都包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x < y \leq n$$$) - 相应轨道的起点和终点的索引。保证每个点最多有两条轨道开始。可能存在起点和终点都重合的赛道。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 $$$k$$$ ($$$0 \leq k \leq \frac{4}{7}n$$$) — 要关闭的点的数量。在下一行中,打印 $$$k$$$ 不同的整数 - 以任何顺序关闭的所有点的索引。

如果有多个答案,您可以输出其中任何一个。请注意,您不必最小化 $$$k$$$。可以证明,合适的答案总是存在的。

示例

输入 #1

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

输出 #1

2
3 4 
4
4 5 6 7

注意

在第一个示例案例中,关闭任意两个点是合适的。

在第二个示例案例中,仅平仓现货 $$$1$$$ 也是合适的。