{"trustable":false,"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":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \n \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 \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 \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 \u003cp\u003e\n\u003cbr\u003e有n个点(编号从0开始),每个点都有一个非负权值p[i],m条边(保证没有重边),和Q个操作。\n\u003cbr\u003e对于操作有两种类型\n\u003cbr\u003edestroy a b 表示摧毁点a,b之间的边\n\u003cbr\u003equery a 表示从a出发能到的点中,权值比a大权值最大,在权值最大前提下编号最小的点。如果没有这样的点输出-1。\n"}},{"title":"Input","value":{"format":"HTML","content":"\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 \u003cp\u003e\n\u003cbr\u003e多case,每组间会有一个空行,读到文件结束为止\n\u003cbr\u003e第一行一个整数n,第二行n个非负整数表示点的权值\n\u003cbr\u003e第三行一个整数m,之后m行两个整数a,b表示a,b之间有一条边。之后一个整数Q,之后Q行输入格式如题意。\n\u003cbr\u003e1\u003c\u003dn\u003c\u003d10000,p[i]\u003c\u003d1000000000,0\u003c\u003dM\u003c\u003d20000,0\u003c\u003dQ\u003c\u003d50000)\n\n"}},{"title":"Output","value":{"format":"HTML","content":"\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 \u003cp\u003e \n对于每个询问,输出相应的结果。\u003cb\u003e两组测试数据之间输出一个空行\u003c/b\u003e。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\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 \u003cp\u003e\u003cb"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/b\u003e\u003c/p\u003e \n \u003cpre\u003e1\n-1\n-1\n-1\n\u003c/pre\u003e \n "}}]}