P4617 [COCI 2017/2018 #5] Planinarenje

米尔科和斯拉夫科喜欢一起徒步旅行。米尔科喜欢山峰，而斯拉夫科喜欢山谷。因此，每次他们爬到一个山峰时，斯拉夫科决定他们要下到哪个山谷，前提是有通往该山谷的小径。同样地，在每个山谷中，米尔科决定他们要爬上哪个山峰。永远不可能直接从一个山峰爬到另一个山峰，或从一个山谷到另一个山谷。为了使徒步旅行尽可能有趣，他们从不重复访问同一个地点（无论是山峰还是山谷）。一旦他们到达一个只能通往他们之前访问过的地点的地方，他们就会叫山地救援队来接他们。如果最后一个地点是山峰，米尔科获胜；如果是山谷，斯拉夫科获胜。 显然，你已经知道你的任务是什么：如果我们假设他们两个都以最佳方式进行游戏，谁会获胜？请为所有初始山峰回答这个问题。

第一行包含两个正整数，$N$ 和 $M$（$1 \leq N \leq 5000$，$1 \leq M \leq \min(5000, N \cdot N)$）。这里 $N$ 表示山峰和山谷的数量（因此，有 $N$ 个山峰和 $N$ 个山谷），而 $M$ 表示徒步小径的数量。 接下来的 $M$ 行中的每一行包含两个正整数：$v_i$ 和 $d_i$（$1 \leq v_i, d_i \leq N$），表示在山峰 $v_i$ 和山谷 $d_i$ 之间有一条小径。每对山峰和山谷之间最多存在一条小径。

你必须输出 $N$ 行。第 $i$ 行表示如果起点是山峰 $i$，谁是获胜者。

在占总分数 30% 的测试用例中，将满足 $1 \leq N \leq 10$ 和 $1 \leq M \leq N \cdot N$。 在额外占总分数 20% 的测试用例中，对于每两个连接的地点之间，将存在唯一的路径。换句话说，图将是一个森林。 **第二个测试用例的说明：** 从第一个山峰开始，斯拉夫科可以选择去第一个山谷，所以斯拉夫科获胜。 从第二个山峰开始，斯拉夫科可以选择去第二个山谷，之后米尔科通过选择去第四个山峰获胜。 从第三个山峰开始，没有小径，所以米尔科获胜。 从第四个山峰开始，斯拉夫科必须选择去第二个山谷，之后米尔科通过选择第二个山峰获胜。 题面翻译由 ChatGPT-4o 提供。