QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 256 MB 總分: 100

#10554. 让你快乐的问题

统计

Alice 和 Bob 是好朋友,就像其他故事里一样。有一天,Alice 和 Bob 在玩一个有趣的游戏。游戏在一个有 $n$ 个顶点和 $m$ 条边的有向图上进行,Alice 和 Bob 各持有一枚棋子。初始时,Bob 的棋子放在顶点 $x$,Alice 的棋子放在顶点 $y$。Bob 先手,然后是 Alice,接着是 Bob,以此类推。

在每一轮移动中,玩家必须将自己的棋子从当前所在的顶点沿一条有向边移动到相邻的顶点。(请记住,游戏是在有向图上进行的。)如果某人无法进行这样的移动,则该玩家被视为输掉游戏。

此外还有一条规则:在任何时候,如果 Bob 和 Alice 的棋子位于同一个顶点,则 Alice 被视为获胜,游戏立即结束。

现在给定初始状态,请你判断谁会获胜。请注意,Bob 和 Alice 在游戏过程中都不会犯错,即他们都采取最优策略。如果游戏永远不会结束,则认为 Bob 获胜。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

对于每个测试用例,第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 100, 1 \le m \le n \times (n - 1)$)。接下来的 $m$ 行,每行包含两个整数 $b$ 和 $e$,表示存在一条从顶点 $b$ 到顶点 $e$ 的有向边。最后一行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$),分别是 Bob 和 Alice 的初始位置。图中不包含自环或重边。

输出格式

对于每个测试用例,输出一行 “Case #x: y”,其中 $x$ 是测试用例编号(从 1 开始),如果 Bob 能获胜或游戏永远不会结束,则 $y$ 为 “Yes”(不含引号),否则为 “No”(不含引号)。

样例

样例输入 1

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

样例输出 1

Case #1: Yes
Case #2: No
Case #3: Yes

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.