#CF2041K. 营养平衡物种

营养平衡物种

K. 营养平衡物种
时间限制:每个测试点 3 秒
内存限制:每个测试点 128 MB


题目描述

在一个跨学科合作中,一位生态系统科学家和一位计算机科学家联手,利用计算方法分析复杂生态系统的结构。
生态系统科学家将生态系统建模为一个有向图 D=(V,A)D = (V, A),其中每个物种用一个节点 vVv \in V 表示,每个捕食关系用一条有向边 (x,y)A(x, y) \in A 表示,从猎物 xx 指向捕食者 yy
这种图结构使他们能够模拟能量在生态系统中从一种物种流向另一种物种的过程。

定义了生态系统的两个重要特征:

  • 独立营养组:一组物种 SS 被称为独立营养组,如果不存在 xSx \in S 可以通过一系列有向捕食关系到达 SS 中的另一个物种 ySy \in Syxy \neq x),即在 DD 中不存在从 xxyy 的有向路径。

  • 营养平衡物种:一个物种被称为营养平衡物种,如果它能够到达的物种数量(通过有向路径,不包括自身)与能够到达它的物种数量(通过有向路径,不包括自身)几乎相等
    具体来说,营养平衡物种是所有物种中,上述两个数量之差的绝对值最小的物种。


示例说明

考虑一个包含 n=4n = 4 个物种、m=3m = 3 条捕食关系的生态系统:

  • 物种 1:草(节点 1)
  • 物种 2:兔子(节点 2)
  • 物种 3:狐狸(节点 3)
  • 物种 4:鹰(节点 4)

捕食关系有向边:

  • (1,2)(1, 2):草被兔子吃
  • (2,3)(2, 3):兔子被狐狸吃
  • (2,4)(2, 4):兔子也被鹰吃

现在考虑集合 S={3,4}S = \{3, 4\}(狐狸和鹰)。狐狸(节点 3)和鹰(节点 4)之间不存在有向路径:狐狸不能到达鹰,鹰也不能到达狐狸。因此,这个集合是一个独立营养组。

各物种分析

  • 物种 1(草):
    可到达:3 个(兔子、狐狸、鹰)
    被到达:0 个(无)
    绝对差:30=3|3 - 0| = 3

  • 物种 2(兔子):
    可到达:2 个(狐狸、鹰)
    被到达:1 个(草)
    绝对差:21=1|2 - 1| = 1

  • 物种 3(狐狸):
    可到达:0 个
    被到达:2 个(草、兔子)
    绝对差:02=2|0 - 2| = 2

  • 物种 4(鹰):
    可到达:0 个
    被到达:2 个(草、兔子)
    绝对差:02=2|0 - 2| = 2

在这些物种中,兔子的绝对差最小,为 11,因此兔子是生态系统中的营养平衡物种。


已知条件

已知该生态系统中任何一个独立营养组的大小最多为 kk
你需要找出该生态系统中所有的营养平衡物种。


输入格式

第一行包含两个整数 nnmm,分别表示有向图 DD 的节点数(物种数)和边数(捕食关系数)。节点编号为 1,2,,n1, 2, \dots, n
接下来 mm 行,每行包含两个整数 xix_iyiy_i,表示一条从 xix_iyiy_i 的有向边。

数据范围:

  • 1n2×1051 \le n \le 2 \times 10^5
  • 0mmin{n(n1),4×105}0 \le m \le \min\{n(n-1), 4 \times 10^5\}
  • kk 不是输入值,但保证对于每个测试数据,1k161 \le k \le 16
  • 1xi,yin1 \le x_i, y_i \le nxiyix_i \ne y_i
  • 每个有序对 (xi,yi)(x_i, y_i) 在输入中最多出现一次

输出格式

输出一行,按升序输出所有营养平衡物种的节点编号。相邻节点编号之间用一个空格隔开。


输入输出样例

样例输入 1

4 3
1 2
2 3
2 4

样例输出 1

2

样例输入 2

4 5
1 2
1 3
1 4
2 3
3 2

样例输出 2

2 3 4