← 返回题目列表

AtCoder · pakencamp_2022_day2_a

A. 场地

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

配点 : 300 点

問題文

帕研王国由 N 个城市以及连接这些城市的 M 条道路组成。城市按照海拔从高到低依次编号为 1, 2, \ldots, N ,所有道路都可以从海拔较高的城市向海拔较低的城市单向通行。具体来说,第 i 条道路可以从城市 A_i 向城市 B_i 单向通行。 (A_i < B_i) 。

现在,今年的帕研集训也将要举办了。今年的帕研集训将在若干个城市设置会场,使得从帕研王国的任意城市出发,都可以通过通行 0 条以上的道路移动到设有会场的城市。

然而,由于预算有限,我们希望设置会场的城市尽可能少。请确定一个设置会场的城市集合。

制約

  • 输入中的所有数值均为整数
  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i < B_i \leq N (1 \leq i \leq M)

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

1 在第1行中,输出将设置场地的城镇数量。这需要是满足条件的场馆设置城市数量可以考虑的最小值。 在

2 行中,输入举办场地的城市,以空格分隔。按升序排列输出。


入力例 1

4 4
1 2
1 3
1 4
2 4

出力例 1

2
3 4

在此示例输出中,您可以从每个城市移动到场地所在的城市,如下所示。

  • 街 1 从城市出发 您可以移至 3, 4 可以移动到
  • 街 2 从城市出发 您可以移至 4 可以移动到
  • 街 3 从城市出发 您可以移至 3 可以移动到
  • 街 4 从城市出发 您可以移至 4 可以移动到

还有,场地 1 此输出满足条件,因为不可能在少于一个城镇中建立并从每个城镇移动到场地所在的城镇。 小于或等于


入力例 2

10 20
4 6
7 9
1 8
4 7
2 3
5 6
5 8
8 10
8 9
3 4
7 8
3 6
1 2
4 9
8 10
6 10
5 9
2 7
6 10
1 8

出力例 2

2
9 10