{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eA thief is running away!\u003cbr\u003eWe can consider the city where he locates as an undirected graph in which nodes stand for crosses and edges stand for streets. The crosses are labeled from 0 to N–1. \u003cbr\u003eThe tricky thief starts his escaping from cross S. Each moment he moves to an adjacent cross. More exactly, assume he is at cross u at the moment t. He may appear at cross v at moment t + 1 if and only if there is a street between cross u and cross v. Notice that he may not stay at the same cross in two consecutive moment.\u003cbr\u003eThe cops want to know if there’s some moment at which it’s possible for the thief to appear at any cross in the city.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input contains multiple test cases:\u003cbr\u003eIn the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given. \u003cbr\u003eFor any test case, the first line contains three integers N (≤ 100 000), M (≤ 500 000), and S. N is the number of crosses. M is the number of streets and S is the index of the cross where the thief starts his escaping.\u003cbr\u003eFor the next M lines, there will be 2 integers u and v in each line (0 ≤ u, v \u0026lt; N). It means there’s an undirected street between cross u and cross v.\u003cbr\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line to tell if there’s a moment that it’s possible for the thief to appear at any cross. Look at the sample output for output format.\u003cbr\u003e\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 3 0\r\n0 1\r\n0 2\r\n1 2\r\n2 1 0\r\n0 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: YES\r\nCase 2: NO\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"For the first case, just look at the table below. (YES means the thief may appear at the cross at that moment)\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/dd4db538a4d818d70981808053c6576a?v\u003d1715467424\"\u003e\u003c/center\u003e \u003cbr\u003eFor the second input, at any moment, there’s at least one cross that the thief can’t reach."}}]}