AT_abc241_g [ABC241G] Round Robin

题目描述

编号为 $1$ 到 $N$ 的 $N$ 个人正在进行一场循环赛。
也就是说，对于所有的组合 $(i,j)\ (1\leq i < j \leq N)$，人 $i$ 和人 $j$ 都会进行一次比赛，因此比赛总共会进行 $\frac{N(N-1)}{2}$ 场。
此外，每场比赛必定有一方获胜，另一方失败，不会出现平局。

现在已经有 $M$ 场比赛结束，第 $i$ 场比赛中，人 $W_i$ 战胜了人 $L_i$。

请列举出在循环赛全部结束后，有可能单独获得冠军的人。
这里的“单独冠军”指的是，该人的胜场数比其他任何人的胜场数都多。

输入格式

输入以如下格式从标准输入读入。

$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<A_2<\dots<A_K)$，请按升序、空格分隔输出 $A$。
即，输出格式如下：

$A_1$ $A_2$ $\dots$ $A_K$

输入输出样例 #1

输入 #1

4 2
2 1
2 3

输出 #1

2 4

输入输出样例 #2

输入 #2

3 3
1 2
2 3
3 1

输出 #2

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$
• 若 $i\neq j$，则 $(W_i,L_i) \neq (W_j,L_j)$
• $(W_i,L_i) \neq (L_j,W_j)$
• 所有输入均为整数

样例解释 1

人 $2,4$ 有可能单独获得冠军，人 $1,3$ 不可能单独获得冠军。注意，像 4 2 这样的输出是不正确的。

样例解释 2

也有可能没有任何人有可能单独获得冠军。

由 ChatGPT 4.1 翻译