{"trustable":false,"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":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv id\u003d\"problem-body\"\u003e \n \u003cp\u003eTo help capture criminals on the run, the police are introducing a new computer system. The area covered by the police contains \u003cstrong\u003eN\u003c/strong\u003e cities and \u003cstrong\u003eE\u003c/strong\u003e bidirectional roads connecting them. The cities are labelled 1 to \u003cstrong\u003eN\u003c/strong\u003e. The police often want to catch criminals trying to get from one city to another. Inspectors, looking at a map, try to determine where to set up barricades and roadblocks.\u003c/p\u003e \n \u003cp\u003eThe new computer system should answer the following two types of queries:\u003c/p\u003e \n \u003cp\u003e1. Consider two cities \u003cstrong\u003eA\u003c/strong\u003e and \u003cstrong\u003eB\u003c/strong\u003e, and a road connecting cities \u003cstrong\u003eG\u003csub\u003e1\u003c/sub\u003e\u003c/strong\u003e and \u003cstrong\u003eG\u003csub\u003e2\u003c/sub\u003e\u003c/strong\u003e. Can the criminals get from city \u003cstrong\u003eA\u003c/strong\u003e to city \u003cstrong\u003eB\u003c/strong\u003e if that one road is blocked and the criminals can\u0027t use it?\u003c/p\u003e \n \u003cp\u003e2. Consider three cities \u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e and \u003cstrong\u003eC\u003c/strong\u003e. Can the criminals get from city \u003cstrong\u003eA\u003c/strong\u003e to city \u003cstrong\u003eB\u003c/strong\u003e if the entire city \u003cstrong\u003eC\u003c/strong\u003e is cut off and the criminals can\u0027t enter that city?\u003c/p\u003e \n \u003cp\u003eWrite a program that implements the described system.\u003c/p\u003e \n \u003ch3\u003eInput\u003c/h3\u003e \n \u003cp\u003eThe first line contains two integers \u003cstrong\u003eN\u003c/strong\u003e and \u003cstrong\u003eE\u003c/strong\u003e (2 ≤ N ≤ 10\u003csup\u003e5\u003c/sup\u003e, 1 ≤ E ≤ 5*10\u003csup\u003e5\u003c/sup\u003e), the number of cities and roads. Each of the following \u003cstrong\u003eE\u003c/strong\u003e lines contains two distinct integers between 1 and \u003cstrong\u003eN\u003c/strong\u003e – the labels of two cities connected by a road. There will be at most one road between any pair of cities.\u003c/p\u003e \n \u003cp\u003eThe following line contains the integer \u003cstrong\u003eQ\u003c/strong\u003e (1 ≤ Q ≤ 10\u003csup\u003e5\u003c/sup\u003e), the number of queries the system is being tested on. Each of the following \u003cstrong\u003eQ\u003c/strong\u003e lines contains either four or five integers. The first of these integers is the type of the query – \u003cstrong\u003e1\u003c/strong\u003e or \u003cstrong\u003e2\u003c/strong\u003e.\u003c/p\u003e \n \u003cp\u003eIf the query is of \u003cstrong\u003etype 1\u003c/strong\u003e, then the same line contains four more integers \u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e, \u003cstrong\u003eG\u003csub\u003e1\u003c/sub\u003e\u003c/strong\u003e and \u003cstrong\u003eG\u003csub\u003e2\u003c/sub\u003e\u003c/strong\u003e as described earlier. \u003cstrong\u003eA\u003c/strong\u003e and \u003cstrong\u003eB\u003c/strong\u003e will be different. \u003cstrong\u003eG\u003csub\u003e1\u003c/sub\u003e\u003c/strong\u003e and \u003cstrong\u003eG\u003csub\u003e2\u003c/sub\u003e\u003c/strong\u003e will represent an existing road.\u003c/p\u003e \n \u003cp\u003eIf the query is of \u003cstrong\u003etype 2\u003c/strong\u003e, then the same line contains three more integers \u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e and \u003cstrong\u003eC\u003c/strong\u003e. \u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e and \u003cstrong\u003eC\u003c/strong\u003e will be distinct integers.\u003c/p\u003e \n \u003cp\u003eThe test data will be such that it is initially possible to get from each city to every other city.\u003c/p\u003e \n \u003ch3\u003eOutput\u003c/h3\u003e \n \u003cp\u003eOutput the answers to all \u003cstrong\u003eQ\u003c/strong\u003e queries, one per line. The answer to a query can be \u003cem\u003eda\u003c/em\u003e (yes) or \u003cem\u003ene\u003c/em\u003e (no).\u003c/p\u003e \n \u003ch3\u003eExample\u003c/h3\u003e \n \u003cpre style\u003d\"text-align: left;\"\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\u003cbr\u003e13 15\u003cbr\u003e1 2\u003cbr\u003e2 3\u003cbr\u003e3 5\u003cbr\u003e2 4\u003cbr\u003e4 6\u003cbr\u003e2 6\u003cbr\u003e1 4\u003cbr\u003e1 7\u003cbr\u003e7 8\u003cbr\u003e7 9\u003cbr\u003e7 10\u003cbr\u003e8 11\u003cbr\u003e8 12\u003cbr\u003e9 12\u003cbr\u003e12 13\u003cbr\u003e5\u003cbr\u003e1 5 13 1 2\u003cbr\u003e1 6 2 1 4\u003cbr\u003e1 13 6 7 8\u003cbr\u003e2 13 6 7\u003cbr\u003e2 13 6 8\u003cbr\u003e\u003cbr\u003e\u003cstrong\u003eOutput:\u003c/strong\u003e\u003cbr\u003eda\u003cbr\u003eda\u003cbr\u003eda\u003cbr\u003ene\u003cbr\u003eda\u003c/pre\u003e \n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}}]}