P8943 Deception Point

“The air defense fire net is online.” Delta Two shouted. Sitting in the weapon control seat by the door of the “Kiowa” armed helicopter, he raised his thumb. “The fire net, modulated noise, and cover pulses are all activated and locked.” Delta One understood at once. He jerked the aircraft into a sharp right bank, and the aircraft returned to a straight route toward “Goya.” This move could avoid “Goya”’s radar surveillance. “Chaff pack confirmed!” Delta Two shouted. > Absolute isolation, Delta One thought. > They have no resistance at all. Their targets had escaped from the Milne Ice Shelf, lucky and cunning, but this time they would not get away again. Rachel Sexton and Michael Tolland chose to abandon the shore and board the ship, a terrible choice. But this would be the last bad decision they ever made.

Rachel and Michael are trapped on the “Goya,” and Delta Two is hunting them by following the radar. Luckily, Rachel also has a radar, so both sides can know each other’s positions. Inside the ship there are $n$ rooms, and there are $n$ corridors connecting these rooms. The $n$ rooms are connected to each other. Because the ship is cramped, there will be no cycles of length at most $4$ inside the ship. Every minute, Rachel and Delta Two will simultaneously run from one room to another room. If Rachel encounters Delta in a room or on a corridor, it means the end is near. Rachel has a total of $q$ questions: when she is in room $x$ and Delta Two is in room $y$, can she survive? --- #### **[Formal Statement]** Given an undirected connected graph with $n$ vertices and $n$ edges, and there are no cycles of length $4$ (or less). There are $q$ queries $x, y$. Place two tokens $\rm A, B$ on vertices $x, y$ of the graph. In each turn, both players simultaneously move their token one step along an edge. If the two tokens move to the same vertex at the same time, or traverse the same edge at the same time, then $\rm B$ wins. If after $10^{10^{9961}}$ turns $\rm B$ still has not won, then $\rm A$ wins. Both $\rm A$ and $\rm B$ are extremely smart, and they will not make decisions that are bad for themselves. Please determine the result of each game. If $\rm A$ wins, output `Survive`; otherwise output `Deception`. **If you have questions about the statement, please refer to the sample explanation and the Constraints section.**

The first line contains two integers $n, q$. The next $n$ lines each contain two integers $u_i, v_i$, indicating that there is a corridor between room $u_i$ and room $v_i$. Then follow $q$ lines, each containing two integers $x_i, y_i$, indicating one query.

Output $q$ lines. For each query, if Rachel can survive, output `Survive`; otherwise output `Deception`.

#### [Sample Explanation] The ship cabin graph is as follows:  In the second query, Delta can move first to vertex $2$, while Rachel moves to vertex $4$. Then it can be proven that there is no strategy that allows Rachel to avoid encountering Delta. #### [Constraints] **This problem uses bundled testdata.** | $\text{Subtask}$ | Score | $n\le$ | $q\le$ | Special Property | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $5$ | $2\times10^5$ | $1$ | None | | $1$ | $5$ | $10$ | $2\times10^5$ | None | | $2$ | $5$ | $2\times 10^5$ | $2\times10^5$ | $\forall 1\le i\le n, u_i=i,v_i=(i\bmod n) + 1$ | | $3$ | $15$ | $200$ | $2\times 10^5$ | None | | $4$ | $20$ | $2\times 10^3$ | $2\times 10^5$ | None | | $5$ | $50$ | $2\times 10^5$ | $2\times 10^5$ | None | For $100\%$ of the data, $3\le n\le 2\times10^5$, $1\le q\le2\times10^5$, $u_i\neq v_i$, $x_i\neq y_i$. There are no cycles of length $4$ (or less). Translated by ChatGPT 5