P14615 [2019 KAIST RUN Fall] Capital

给定由 $M$ 条道路连接的 $N$ 个城市。城市编号从 $1$ 到 $N$，道路编号从 $1$ 到 $M$。对于任意两个城市，都存在一系列道路连接这两个城市。道路 $i$ 的长度为 $L_i$ 公里，并双向连接城市 $A_i$ 和城市 $B_i$。每条道路的长度均为正数，即 $L_i > 0$。不幸的是，你忘记了每条道路的具体长度。 你观察到，对于每条道路 $i$，所有在该道路上的人都从 $A_i$ 单向前往 $B_i$。因此，你提出了以下假设： - 存在一个称为 $S$ 的首都城市。 - 人们从首都城市前往其他城市。 - 人们尝试沿最短路径移动。因此从 $S$ 到 $A_i$ 的最短路径长度小于等于从 $S$ 到 $B_i$ 的最短路径长度。 当你可以将每条道路的长度任意分配为正实数时，能否找到满足条件的首都城市 $S$？你可以假设至少存在一个城市满足条件。

输入的第一行包含两个整数 $N$（$2 \le N \le 500$）和 $M$（$N-1 \le M \le \frac{N(N-1)}{2}$）。 接下来的 $M$ 行中，第 $i$ 行给出 $A_i$ 和 $B_i$（$1 \le A_i, B_i \le N$）。 输入中不存在自环或重边。形式化地说，$A_i \ne B_i$，且 $\{A_i, B_i\} = \{A_j, B_j\} \implies i = j$。

第一行输出可能的首都城市数量 $K$。 第二行以递增顺序输出 $K$ 个用空格分隔的整数，表示所有可能作为首都的城市。

翻译由 DeepSeek V3 完成