题目描述

你负责一个绝密政府研究设施的安全工作。最近，你的政府捕获了一个活生生的外星生命形式，并为同行研究人员举办了一个开放日活动。当然，并非所有的客人都值得信任，所以为他们分配了不同的安全许可级别。只有安全级别为 5 的客人才能进入关押外星生物的实验室；除此之外，其他客人可以在设施的其余部分自由参观。该设施中的每个房间都通过单向气密门相连，这意味着你只能沿一个方向通过这些门。

为了保护珍贵的外星生物，你将在通往关押外星生物房间的路线上设置加强的安全措施（以武装警卫的形式），但警卫不设置在关押外星生物的房间内，因为警卫没有足够的许可进入该房间。

警卫会检查所有试图通过他们所驻守房间的客人的身份和安全级别，所以你希望将警卫部署在对那些无意参观外星生物的客人造成最小困扰的地方。因此，必须部署警卫的房间需满足以下两个条件：

1. 为了到达关押外星生物的房间，客人必须经过部署有警卫的房间；
2. 不存在其他具有此属性且更靠近关押外星生物房间的房间，要记住，警卫不能部署在关押外星生物的房间内。

下面的图表展示了你的设施的一种可能布局：

请注意，将警卫部署在房间 2 会满足第一个条件，但房间 3 更靠近外星生物所在的房间，所以警卫必须部署在房间 3。

输入格式

所有客人都从房间 0 进入，即设施的入口。你的程序接受一系列包含整数的行。第一行包含两个整数：房间的数量，以及关押外星生物的房间号（当然，外星生物是自愿待在那里的）。

输入的其余部分是一系列仅包含两个整数的行，指定气密门的位置。这些行中的第一个数字表示源房间，第二个数字表示目标房间。记住：你只能从源房间前往目标房间。

输出格式

你的程序的输出仅包含一行：

Put guards in room N.

其中 N 是你决定部署警卫的房间号。

9 4
0 2
2 3
3 4
5 3
5 4
3 6
6 5
6 7
6 8
4 7
0 1
1 7
7 0

Put guards in room 3.

来源

2001年南非