← 返回题目列表

AtCoder · abc241_g

G. 循环赛

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

分数: 600 点

问题陈述

N 玩家编号 1 通过 N 将参加循环赛。
具体来说,对于每对 (i,j) (1\leq i \lt j \leq N),玩家 i 和玩家 j 双方进行一场比赛,总计 \frac{N(N-1)}{2} 匹配。
每场比赛中,一名玩家将获胜,另一名玩家将成为失败者;没有平局。

M 比赛已经结束。 在 i第场比赛,玩家 W_i 赢得玩家 L_i.

列出循环赛结束后所有可能成为唯一获胜者的选手。
如果某个玩家的获胜次数严格大于任何其他玩家,则该玩家被称为唯一获胜者。

约束

  • 2\leq N \leq 50
  • 0\leq M \leq \frac{N(N-1)}{2}
  • 1\leq W_i,L_i\leq N
  • W_i \neq L_i
  • If i\neq j,那么 (W_i,L_i) \neq (W_j,L_j).
  • (W_i,L_i) \neq (L_j,W_j)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
W_1 L_1
W_2 L_2
\vdots
W_M L_M

输出

让 A=(A_1,A_2,\dots,A_K) (A_1\lt A_2 \lt \dots \lt A_K) 是可能成为唯一获胜者的玩家的索引集。 打印 A 按升序排列,中间有空格。
换句话说,按以下格式打印。

A_1 A_2 \dots A_K

示例输入 1

4 2
2 1
2 3

示例输出 1

2 4

玩家 2 和 4 可能成为唯一的获胜者,而玩家 1 和 3 不能。
请注意,输出如下 4 2 被认为是不正确的。


示例输入 2

3 3
1 2
2 3
3 1

示例输出 2


可能没有玩家能够成为唯一的获胜者。


示例输入 3

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

示例输出 3

1 3 6 7