#P5384. 危机

危机

Description

魔法学院最近面临一场危机,黑暗巫师正在集结力量准备进攻学院。作为应对措施,学院需要在各个魔法塔之间快速传递消息。 学院共有 $n$ 座魔法塔,通过 $n - 1$ 条魔法传送通道相互连接,每条传送通道的传送时间相同(可以看作是 1 个单位时间)。这些魔法塔和通道构成了一个完整的魔法网络。 现在,学院院长位于编号为 $x$ 的魔法塔,而情报官位于编号为 $y$ 的魔法塔。他们都以最快的速度通过传送通道向对方移动(移动速度相同)。 你需要判断:院长和情报官是会在一座魔法塔内相遇,还是在传送通道上相遇?

Input Format

第一行包含一个整数 $n$,表示魔法塔的数量。 接下来的 $n - 1$ 行,每行包含两个整数 $u$ 和 $v$,表示编号为 $u$ 和 $v$ 的魔法塔之间存在一条传送通道。 然后是一个整数 $q$,表示询问的次数。 接下来的 $q$ 行,每行包含两个整数 $z$ 和 $y$,分别表示院长和情报官所在的魔法塔编号。

Output Format

对于每个询问,输出一行答案: 

- 如果他们会在魔法塔内相遇,输出 `Meet at the tower!` 

- 如果他们会在传送通道上相遇,输出 `Meeting on the passage!`

4
1 2
2 3
2 4
3
1 2
1 3
1 4
Meeting on the passage!
Meet at the tower!
Meet at the tower!

Hint

- 对于 20% 的数据:$2 \leq n, q \leq 10$ 

- 对于 40% 的数据:$2 \leq n, q \leq 1000$ 

- 对于 60% 的数据:$2 \leq n \leq 3000, 2 \leq q \leq 10^5$ 

- 对于 100% 的数据:$2 \leq n, q \leq 10^5$

Source

大湾区初中组