{"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\r\n\u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e\u003ctbody\u003e\u003ctr class\u003d\"navigation\"\u003e\r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/OTOCI/en/\"\u003eEnglish\u003c/a\u003e\u003c/td\u003e \r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/OTOCI/vn/\"\u003eVietnamese\u003c/a\u003e\u003c/td\u003e \r\n\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\r\n\r\n\r\n\u003cp\u003eSome time ago Mirko founded a new tourist agency named \"Dreams of Ice\". The agency purchased N\r\nicy islands near the South Pole and now offers excursions. Especially popular are the emperor\r\npenguins, which can be found in large numbers on the islands.\u003c/p\u003e\r\n\u003cp\u003eMirko\u0027s agency has become a huge hit; so big that it is no longer cost-effective to use boats for the\r\nexcursions. The agency will build bridges between islands and transport tourists by buses. Mirko\r\nwants to introduce a computer program to manage the bridge building process so that fewer mistakes\r\nare made.\u003c/p\u003e\r\n\u003cp\u003eThe islands are numbered 1 through N. No two islands are initially connected by bridges. The initial\r\nnumber of penguins on each island is known. That number may change, but will always be between 0\r\nand 1000 (inclusive).\u003c/p\u003e\r\n\u003cp\u003eYour program must handle the following three types of commands:\r\n\u003c/p\u003e\u003cul\u003e\r\n\u003cli\u003e\"bridge A B\" – an offer was received to build a bridge between islands A and B (A and B will\r\nbe different). To limit costs, your program must accept the offer only if there isn\u0027t already a\r\nway to get from one island to the other using previously built bridges. If the offer is accepted,\r\nthe program should output \"yes\", after which the bridge is built. If the offer is rejected, the\r\nprogram should output \"no\".\u003c/li\u003e\r\n\u003cli\u003e\"penguins A X\" – the penguins on island A have been recounted and there are now X of them.\r\nThis is an informative command and your program does not need to respond.\u003c/li\u003e\r\n\u003cli\u003e\"excursion A B\" – a group of tourists wants an excursion from island A to island B. If the\r\nexcursion is possible (it is possible to get from island A to B), the program should output the\r\ntotal number of penguins the tourists would see on the excursion (including islands A and B).\r\nOtherwise, your program should output \"impossible\".\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line contains the integer N (1 ≤ N ≤ 30 000), the number of islands.\u003c/p\u003e\r\n\u003cp\u003eThe second line contains N integers between 0 and 1000, the initial number of penguins on each of the\r\nislands.\u003c/p\u003e\r\n\u003cp\u003eThe third line contains an integer Q (1 ≤ Q ≤ 300 000), the number of commands.\u003c/p\u003e\r\n\u003cp\u003eQ commands follow, each on its own line.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eOutput the responses to commands \"bridge\" and \"excursion\", each on its own line.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\r\n4 2 4 5 6\r\n10\r\nexcursion 1 1\r\nexcursion 1 2\r\nbridge 1 2\r\nexcursion 1 2\r\nbridge 3 4\r\nbridge 3 5\r\nexcursion 4 5\r\nbridge 1 3\r\nexcursion 2 4\r\nexcursion 2 5\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\nimpossible\r\nyes\r\n6\r\nyes\r\nyes\r\n15\r\nyes\r\n15\r\n16\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e6\r\n1 2 3 4 5 6\r\n10\r\nbridge 1 2\r\nbridge 2 3\r\nbridge 4 5\r\nexcursion 1 3\r\nexcursion 1 5\r\nbridge 3 4\r\nexcursion 1 5\r\npenguins 3 10\r\nexcursion 1 3\r\nbridge 1 5\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eyes\r\nyes\r\nyes\r\n6\r\nimpossible\r\nyes\r\n15\r\n13\r\nno\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\n\u003c/div\u003e"}}]}