← 返回题目列表

Codeforces · 1019/C

C. 谢尔盖的问题

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

谢尔盖刚刚五岁了!当他一岁的时候,他的父母给了他一个号码;当他两岁时,他的父母给了他一个整数数组。三岁生日那天,他收到了一根绳子。当他四岁的时候,他的母亲轻声叫醒他,希望他做一个好孩子,并送给他一棵有根的树。今天他又过生日了!他发现了一个没有循环的有向图作为父母送给他的礼物。

由于谢尔盖是一个非常好奇的男孩,他立即想出了一件事要做。他决定在该图中找到一组 $$$Q$$$ 顶点,使得 Q$$$ 中的两个顶点 $$$x, y 不通过边连接,并且可以在不超过两次的移动时间内从 $$$Q$$$ 的某个顶点到达任何顶点 $$$z \notin Q$$$。

经过一番思考,Sergey 解决了这个任务。你也能解决吗?

如果存在有向边 $$$(x,y)$$$,或者对于某个顶点 $$$z$$$ 存在两个有向边 $$$(x,z)$$$ 和 $$$(z, y)$$$,则顶点 $$$y$$$ 最多可以在两次移动中从顶点 $$$x$$$ 到达。

输入

输入的第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 1\,000\,000$$$, $$$1 \le m \le 1\,000\,000$$$) — 有向图中的顶点数和边数。

以下 $$$m$$$ 行中的每一行都描述了相应的边缘。每个包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) - 第 $$$i$$$ 条边的开始和结束。该图可以在同一对顶点之间包含多条边。

输出

首先打印数字 $$$k$$$ — 选定顶点的数量。然后打印 $$$k$$$ 不同的整数 - 所选顶点的索引。

如果存在多个答案,您可以输出其中任何一个。特别是,您不必最小化集合中的顶点数量。保证总是至少有一组有效的。

示例

输入 #1

5 4
1 2
2 3
2 4
2 5

输出 #1

4
1 3 4 5

输入 #2

3 3
1 2
2 3
3 1

输出 #2

1
3

注意

在第一个示例中,顶点 $$$1, 3, 4, 5$$$ 未连接。顶点 $$$2$$$ 可以通过一条边从顶点 $$$1$$$ 到达。

在第二个示例中,可以一次移动到达顶点 $$$1$$$,两次移动到达顶点 $$$2$$$。

下图说明了示例测试及其答案。