T533492 「GFOI Round 2」Jom & Terry (English ver.)

**[Chinese statement](https://www.luogu.com.cn/problem/P11280). You must submit your code at the Chinese version of the statement.** I am solving [#3406. 「2020-2021 集训队作业」Tom & Jerry](https://loj.ac/p/3406)...... You are right, but: > 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 and Jom are playing a game on an undirected connected graph with $n$ nodes and $m$ edges, which has a designated "root" node $r$. The game follows these rules: - Terry moves first. - The two players take turns moving along the edges of the graph, with each move traversing one edge (or they can choose to "rest" and do nothing). - Terry cannot move to the node where Jom is currently located (Terry is only considered "caught" if he voluntarily moves to the same node as Jom; it is allowed for both to move to the same node $u$ within the same turn, as long as Terry goes there first). Given $q$ queries, each specifying the starting positions $a$ and $b$ of Terry and Jom respectively, determine whether Terry can reach the root node $r$.

无

无

#### Subtasks and Constraints | Subtask ID | $n, m, q \le$ | Special Properties | Score | | :--------: | :-----------: | :--------------: | :--------: | | $0$ | $10^6$ | A | $1$ | | $1$ | $10$ | No | $9$ | | $2$ | $10^6$ | B | $15$ | | $3$ | $10^6$ | C | $15$ | | $4$ | $10^6$ | No | $60$ | - Special Property A: $q = 0$. - Special Property B: The graph is a chain. - Special Property C: The graph is a star graph. For all tests, it is guaranteed that: - $1 \le n, m \le 10^6$; - $0 \le q \le 10^6$; - $1 \le r, u, v, a, b \le n$; - The given graph is an undirected connected graph.