{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\r\n\r\n\u003cimg src\u003d\"CDN_BASE_URL/48b5bd9c6734b870229f223f012e1e01?v\u003d1725557531\" style\u003d\"float: right\" vspace\u003d\"3\" hspace\u003d\"8\" alt\u003d\"Map\"\u003e\r\n\r\nJedi knights, Qui-Gon Jinn and his young apprentice Obi-Wan Kenobi, are entrusted by Queen Padmé Amidala\r\nto save \u003cb\u003eNaboo\u003c/b\u003e from an invasion by the Trade Federation. They must leave Naboo immediately and go to \u003cb\u003eTatooine\u003c/b\u003e\r\nto pick up the proof of the Federation’s evil design. They then must proceed on to the Republic’s capital\r\nplanet \u003cb\u003eCoruscant\u003c/b\u003e to produce it in front of the Republic’s Senate. To help them in this endeavor, the queen’s captain provides them with an intergalactic map. This map shows connections between planets not yet blockaded by the Trade Federation. Any pair of planets has at most one connection between them, and all the connections are two-way. To avoid detection by enemy spies, the knights must embark on this adventure without visiting any planet more than once. Can you help them by determining if such a path exists?\r\n\u003cbr\u003e\u003cbr\u003e\u003cb\u003eNote\u003c/b\u003e - In the attached map, the desired path is shown in bold.\r\n\r\n\u003c/p\u003e\u003ch3\u003eInput Description\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input is a positive integer t ≤ 20, which is the number of test cases. The descriptions\r\nof the test cases follow one after the other. The first line of each test case is a pair of positive integers\r\nn, m (separated by a single space). 2 ≤ n ≤ 30011 is the number of planets and m ≤ 50011 is the number of connections\r\nbetween planets. The planets are indexed with integers from 1 to n. The indices of Naboo, Tatooine and Coruscant\r\nare 1, 2, 3 respectively. The next m lines contain two integers each, giving pairs of planets that have a\r\nconnection between them.\r\n\r\n\u003c/p\u003e\u003ch3\u003eOutput Description\u003c/h3\u003e\r\n\u003cp\u003eThe output should contain t lines. The i\u003csup\u003eth\u003c/sup\u003e line corresponds to the i\u003csup\u003eth\u003c/sup\u003e test case.\r\nThe output for each test case should be \u003cb\u003eYES\u003c/b\u003e if the required path exists and \u003cb\u003eNO\u003c/b\u003e otherwise.\r\n\r\n\u003c/p\u003e\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003cbr\u003e\r\n2\u003cbr\u003e\r\n3 3\u003cbr\u003e\r\n1 2\u003cbr\u003e\r\n2 3\u003cbr\u003e\r\n1 3\u003cbr\u003e\r\n3 1\u003cbr\u003e\r\n1 3\u003cbr\u003e\r\n\r\n\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003cbr\u003e\r\nYES\u003cbr\u003e\r\nNO\u003cbr\u003e\r\n\n\u003c/p\u003e\u003c/div\u003e"}}]}