QOJ.ac

QOJ

時間限制: 2 s 記憶體限制: 1024 MB 總分: 100

#4703. 兄弟阋墙

统计

你正在和你的哥哥玩一个游戏。

首先,地面上画着一些圆圈,以及连接其中一些圆圈对的箭头。其中两个圆圈分别被标记为起点和终点。

游戏开始时,你位于起点。在游戏的每一轮中,你的哥哥会告诉你一个数字,你必须走相应步数的路程。在每一步中,你选择当前所在圆圈的一条出边,并移动到该箭头指向的圆圈。你可以访问同一个圆圈或使用同一个箭头任意多次。

你的目标是在尽可能少的轮数后停在终点,而你哥哥的目标是尽可能长时间地阻止你。注意,在每一轮中,你必须走完你哥哥告诉你的确切步数。即使你在某一轮中途经过了终点,如果还需要继续走,你也必须离开它。

如果你在走完所有步数之前到达了一个没有出边的圆圈,那么你就输掉了游戏。你还需要注意,你的哥哥可能会无限期地重复回合,让你无法在任何一轮后停下。

你的哥哥虽然刻薄但并不太自私,他认为允许选择任意数字是不公平的。因此,他决定在游戏开始时声明三个数字,并且只使用这三个数字。

现在你的任务是,给定圆圈和箭头的配置,以及声明的三个数字,计算出无论你哥哥如何选择数字,你都能保证完成游戏所需的最少轮数。

输入格式

输入包含一组测试用例,格式如下:

$n \ m \ a \ b \ c$ $u_1 \ v_1$ $\vdots$ $u_m \ v_m$

所有数字均为整数。$n$ 是圆圈的数量 ($2 \le n \le 50$)。圆圈编号为 $1$ 到 $n$。起点和终点分别为 $1$ 和 $n$。$m$ 是箭头的数量 ($0 \le m \le n(n - 1)$)。$a, b, c$ 是你哥哥声明的三个数字 ($1 \le a, b, c \le 100$)。一对 $u_i, v_i$ 表示存在一条从圆圈 $u_i$ 到圆圈 $v_i$ 的箭头。保证对于所有 $i$,$u_i \neq v_i$,且当 $i \neq j$ 时,$u_i \neq u_j$ 或 $v_i \neq v_j$。

输出格式

输出无论你哥哥如何选择数字,你都能保证完成游戏所需的最少轮数。如果你的哥哥可以通过让你无限重复回合或引导你进入一个没有出边的圆圈来阻止你到达终点,则输出 IMPOSSIBLE

样例

样例输入 1

3 3 1 2 4
1 2
2 3
3 1

样例输出 1

IMPOSSIBLE

样例输入 2

8 12 1 2 3
1 2
2 3
1 4
2 4
3 4
1 5
5 8
4 6
6 7
4 8
6 8
7 8

样例输出 2

2

说明

对于样例 1,你的哥哥可以先选 1,然后选 2,并无限重复这些数字。这样你就永远无法完成游戏。

对于样例 2(图 C.1),如果你的哥哥选择 2 或 3,你可以在一轮内完成。如果他选择 1,你将有三个选择:

  • 移动到圆圈 5。这是一个糟糕的主意:你的哥哥随后可以选择 2 或 3 让你输掉游戏。
  • 移动到圆圈 4。这是最佳选择:从圆圈 4 出发,无论下一轮你哥哥选择 1、2 还是 3,你都可以立即完成游戏。
  • 移动到圆圈 2。这对你来说不是最优的。如果下一轮你哥哥选择 1,你还不能完成游戏。总共需要三轮或更多轮。

总之,无论你哥哥如何行动,你都可以在两轮内完成游戏。因此答案是 2。

图 C.1. 样例 2

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.