{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn order to strengthen the defense ability, many stars in galaxy allied together and built many bidirectional tunnels to exchange messages. However, when the Galaxy War began, some tunnels were destroyed by the monsters from another dimension. Then many problems were raised when some of the stars wanted to seek help from the others.\u003c/p\u003e\n\n\u003cp\u003eIn the galaxy, the stars are numbered from 0 to \u003ci\u003eN\u003c/i\u003e-1 and their power was marked by a non-negative integer \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e. When the star \u003ci\u003eA\u003c/i\u003e wanted to seek help, it would send the message to the star with the largest power which was connected with star \u003ci\u003eA\u003c/i\u003e directly or indirectly. In addition, this star should be more powerful than the star \u003ci\u003eA\u003c/i\u003e. If there were more than one star which had the same largest power, then the one with the smallest serial number was chosen. And therefore, sometimes star \u003ci\u003eA\u003c/i\u003e couldn\u0027t find such star for help.\u003c/p\u003e\n\n\u003cp\u003eGiven the information of the war and the queries about some particular stars, for each query, please find out whether this star could seek another star for help and which star should be chosen.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThere are no more than 20 cases. Process to the end of file. \u003c/p\u003e\n\u003cp\u003eFor each cases, the first line contains an integer \u003ci\u003eN\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003eN\u003c/i\u003e \u0026lt;\u003d 10000), which is the number of stars. The second line contains \u003ci\u003eN\u003c/i\u003e integers \u003ci\u003ep\u003csub\u003e0\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ep\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e, ... , \u003ci\u003ep\u003csub\u003en-1\u003c/sub\u003e\u003c/i\u003e (0 \u0026lt;\u003d \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u0026lt;\u003d 1000000000), representing the power of the \u003ci\u003ei\u003c/i\u003e-th star. Then the third line is a single integer \u003ci\u003eM\u003c/i\u003e (0 \u0026lt;\u003d \u003ci\u003eM\u003c/i\u003e \u0026lt;\u003d 20000), that is the number of tunnels built before the war. Then \u003ci\u003eM\u003c/i\u003e lines follows. Each line has two integers \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e (0 \u0026lt;\u003d \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e \u0026lt;\u003d \u003ci\u003eN\u003c/i\u003e - 1, \u003ci\u003ea\u003c/i\u003e !\u003d \u003ci\u003eb\u003c/i\u003e), which means star \u003ci\u003ea\u003c/i\u003e and star \u003ci\u003eb\u003c/i\u003e has a connection tunnel. It\u0027s guaranteed that each connection will only be described once.\u003c/p\u003e\n\u003cp\u003eIn the (\u003ci\u003eM\u003c/i\u003e + 2)-th line is an integer \u003ci\u003eQ\u003c/i\u003e (0 \u0026lt;\u003d \u003ci\u003eQ\u003c/i\u003e \u0026lt;\u003d 50000) which is the number of the information and queries. In the following \u003ci\u003eQ\u003c/i\u003e lines, each line will be written in one of next two formats.\u003c/p\u003e\n\u003cul\u003e\n\u003cp\u003e\u003cb\u003e\u003ci\u003e\"destroy a b\"\u003c/i\u003e\u003c/b\u003e - the connection between star \u003ci\u003ea\u003c/i\u003e and star \u003ci\u003eb\u003c/i\u003e was destroyed by the monsters. It\u0027s guaranteed that the connection between star \u003ci\u003ea\u003c/i\u003e and star \u003ci\u003eb\u003c/i\u003e was available before the monsters\u0027 attack.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e\u003ci\u003e\"query a\"\u003c/i\u003e\u003c/b\u003e - star \u003ci\u003ea\u003c/i\u003e wanted to know which star it should turn to for help\u003c/p\u003e\n\u003c/ul\u003e\n\u003cp\u003eThere is a blank line between consecutive cases.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eFor each query in the input, if there is no star that star a can turn to for help, then output \u003cb\u003e\u003ci\u003e\"-1\"\u003c/i\u003e\u003c/b\u003e; otherwise, output the serial number of the chosen star.\u003c/p\u003e\n\u003cp\u003ePrint a blank line between consecutive cases.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e2\n10 20\n1\n0 1\n5\nquery 0\nquery 1\ndestroy 0 1\nquery 0\nquery 1\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e1\n-1\n-1\n-1\n\u003c/pre\u003e"}}]}