题目描述

Terry 和 Jom 在一个 $n$ 个点 $m$ 条边的有“根”无向连通图上博弈（图的根为 $r$），遵循以下规则：

• Terry 先手；
• 两人轮流在图上移动，每次只能走一条边（也可以睡觉，啥都不干）；
• Terry 不能走到 Jom 所在的结点（我们认为只有 Terry 自投罗网时才会被抓到，即如果 Terry 先移动到结点 $u$ 后 Jom 在同一回合也移动到 $u$ 是合法的）。

给定 $q$ 次询问，每次询问给定 Terry 和 Jom 的起点 $a, b$，你需要回答 Terry 能否到达根（即点 $r$）。

输入格式

第一行包含三个整数 $n, m, r$，表示点数、边数和根的编号；

接下来 $m$ 行，每行包含两个整数 $(u, v)$ 表示一条边（注意可能存在重边或自环）；

接下来一行包含一个整数 $q$，表示询问数；

接下来 $q$ 行，每行包含两个整数 $a, b$，表示 Terry 和 Jom 的起点。

输出格式

首先你应该在开头输出 I'm here!。

接下来 $q$ 行的第 $i$ 行，如果在第 $i$ 次询问中 Terry 能到达根就输出 Terry，否则输出 Jom。

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

I'm here!
Jom
Jom

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

I'm here!
Terry
Terry

提示

【提示】

本题 IO 量较大，请选手使用较快的读入输出方式。

【数据范围】

本题采用捆绑测试。

• 特殊性质 A：$q = 0$。
• 特殊性质 B：保证图是一条链。
• 特殊性质 C：保证图是一个菊花。

对于所有数据，满足：

• $1 \le n, m \le 10^6$；
• $0 \le q \le 10^6$；
• $1 \le r, u, v, a, b \le n$；
• 给定的图是一个无向连通图。