Background

“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.

Problem Description

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.

Input Format

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 Format

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

8 3
2 1
3 1 
4 2 
5 3
6 2
7 5
8 4
5 6
7 8
8 6
3 6

Survive
Deception
Survive

Hint

[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.

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