{"problem":{"name":"Deception Point","description":{"content":"雷切尔与迈克尔被困在了“戈雅”号上，而三角洲二号正在顺着雷达追杀二人。幸运的是，雷切尔也有一副雷达，因此双方都能知道对方的位置。 船舱内部共有 $n$ 个舱室，其中有 $n$ 条走廊连接这些舱室。$n$ 个舱室是互相连通的。由于船上空间拥挤，船舱内不会出现小于等于四条走廊组成的环。每过一分钟，雷切尔与三角洲二号都会同时从一个舱室跑到另一个舱室。 如果雷切尔在舱室内或者过道上碰到了三角洲，那么就","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8943"},"statements":[{"statement_type":"Markdown","content":"雷切尔与迈克尔被困在了“戈雅”号上，而三角洲二号正在顺着雷达追杀二人。幸运的是，雷切尔也有一副雷达，因此双方都能知道对方的位置。\n\n船舱内部共有 $n$ 个舱室，其中有 $n$ 条走廊连接这些舱室。$n$ 个舱室是互相连通的。由于船上空间拥挤，船舱内不会出现小于等于四条走廊组成的环。每过一分钟，雷切尔与三角洲二号都会同时从一个舱室跑到另一个舱室。\n\n如果雷切尔在舱室内或者过道上碰到了三角洲，那么就意味着大限将至。雷切尔总共有 $q$ 个问题：当她在舱室 $x$，且三角洲二号在舱室 $y$ 时，她是否可以存活下来？\n\n---\n\n#### **【形式化题意】**\n\n给定一张 $n$ 个点 $n$ 条边的无向连通图，图内不存在四元（及以下）环。$q$ 次询问 $x,y$，分别在图上 $x,y$ 点上放上棋子 $\\rm A, B$。\n\n每次两人同时操作棋子沿图边移动一步，若两棋子同时走到了同一个点上或者同时走过了相同的边，则 $\\rm B$ 胜利。如果在 $10^{10^{9961}}$ 次操作后 $\\rm B$ 还未胜利，则 $\\rm A$ 胜利。\n\n$\\rm A,B$ 都是绝顶聪明的，他们不会做出对自己不利的决策。请你求出每次游戏的游戏结果。若 $\\rm A$ 获胜，输出 `Survive`；否则输出 `Deception`。\n\n**若对题意有疑问，请移步样例解释与数据范围部分。**\n\n## Input\n\n第一行两个整数 $n,q$。  \n接下来 $n$ 行，每行两个整数 $u_i,v_i$，表示舱室 $u_i$ 与 $v_i$ 之间有一条过道。\n之后 $q$ 行，每行两个整数 $x_i,y_i$，表示一次询问。\n\n## Output\n\n共 $q$ 行。对于每个询问，如果雷切尔可以存活，那么输出 `Survive`，否则输出 `Deception`。\n\n[samples]\n\n## Background\n\n“防空火网已启用。”三角洲二号喊道，他坐在“基奥瓦”武装直升机舱门边的武器控制椅里，竖起了大拇指，“火力网\n、调制噪声、掩护脉冲全都激活并锁定。”\n\n三角洲一号心领神会，驾驶着飞机猛地向右一个侧弯飞机又驶上了一条前往“戈雅”的直线路径。这一招能躲过“戈雅”的雷达监控。\n\n“锡箔包确定！”三角洲二号喊道。\n\n> 绝对的孤立，\n\n三角洲一号想。\n\n> 他们毫无抵抗力。\n\n他们的目标幸运且狡猾地从米尔恩冰架上逃脱了，但这回他们不会再得逞了。雷切尔 · 塞克斯顿和迈克尔 · 托兰选择弃岸上船，真是糟糕的选择。不过，这将是他们所做的最后一个坏决定了。\n\n## Note\n\n#### 【样例解释】\n\n船舱结构图如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/tlsqnsia.png)\n\n在第二组询问中，三角洲可以先走一步到达结点 $2$，此时雷切尔到达结点 $4$。随后可以证明，不存在一种方案使得雷切尔不碰到三角洲。\n\n#### 【数据范围】\n\n**本题开启捆绑测试。**\n\n| $\\text{Subtask}$ | 分值 | $n\\le$ | $q\\le$ | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $0$ | $5$ | $2\\times10^5$ | $1$ | 无 |\n| $1$ | $5$ | $10$ | $2\\times10^5$ | 无 |\n| $2$ | $5$ | $2\\times 10^5$ | $2\\times10^5$ | $\\forall 1\\le i\\le n, u_i=i,v_i=(i\\bmod n) + 1$ |\n| $3$ | $15$ | $200$ | $2\\times 10^5$ | 无 |\n| $4$ | $20$ | $2\\times 10^3$ | $2\\times 10^5$ | 无 |\n| $5$ | $50$ | $2\\times 10^5$ | $2\\times 10^5$ | 无 |\n\n对于 $100\\%$ 的数据，$3\\le n\\le 2\\times10^5$，$1\\le q\\le2\\times10^5$，$u_i\\neq v_i$，$x_i\\neq y_i$。不存在四（及以下）元环。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8943","tags":["2023","洛谷原创","O2优化","最短路","基环树"],"sample_group":[["8 3\n2 1\n3 1 \n4 2 \n5 3\n6 2\n7 5\n8 4\n5 6\n7 8\n8 6\n3 6","Survive\nDeception\nSurvive\n"]],"created_at":"2026-03-03 11:09:25"}}