题目背景

English statement. You must submit your code at the Chinese version of the statement.

我在做 #3406. 「2020-2021 集训队作业」Tom & Jerry……

你说得对，但是：

Tom and Jerry is an American animated media franchise and series of comedy short films created in 1940 by William Hanna and Joseph Barbera. Best known for its 161 theatrical short films by Metro-Goldwyn-Mayer, the series centers on the rivalry between the titular characters of a cat named Tom and a mouse named Jerry. Many shorts also feature several recurring characters.

In its original run, Hanna and Barbera produced 114 Tom and Jerry shorts for MGM from 1940 to 1958. During this time, they won seven Academy Awards for Best Animated Short Film, tying for first place with Walt Disney's Silly Symphonies with the most awards in the category. After the MGM cartoon studio closed in 1957, MGM revived the series with Gene Deitch directing an additional 13 Tom and Jerry shorts for Rembrandt Films from 1961 to 1962. Tom and Jerry became the highest-grossing animated short film series of that time, overtaking Looney Tunes. Chuck Jones produced another 34 shorts with Sib Tower 12 Productions between 1963 and 1967. Five more shorts have been produced since 2001, making a total of 166 shorts.

A number of spin-offs have been made, including the television series The Tom and Jerry Show (1975), The Tom and Jerry Comedy Show (1980–1982), Tom & Jerry Kids (1990–1993), Tom and Jerry Tales (2006–2008), and The Tom and Jerry Show (2014–2021). In 1992, the first feature-length film based on the series, Tom and Jerry: The Movie, was released. 13 direct-to-video films have been produced since 2002. In 2021, a a live-action/animated hybrid film was released. In 2019, a musical adaptation of the series, titled Tom and Jerry: Purr-Chance to Dream, debuted in Japan, in advance of Tom and Jerry's 80th anniversary.

题目描述

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 量较大，请选手使用较快的读入输出方式。

【数据范围】

本题采用捆绑测试。

子任务编号	$n, m, q \le$	特殊性质	分值
$0$	$10^6$	A	$1$
$1$	$10$	无	$9$
$2$	$10^6$	B	$15$
$3$		C
$4$		无	$60$

• 特殊性质 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$；
• 给定的图是一个无向连通图。