{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"epigraph\"\u003e\u003cdiv class\u003d\"epigraph-text\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eDon\u0027t you tell me what you think that I can be\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cp\u003eIf you say that Arkady is a bit old-fashioned playing checkers, you won\u0027t be right. There is also a modern computer game Arkady and his friends are keen on. We won\u0027t discuss its rules, the only feature important to this problem is that each player has to pick a distinct hero in the beginning of the game.\u003c/p\u003e\u003cp\u003eThere are $$$2$$$ teams each having $$$n$$$ players and $$$2n$$$ heroes to distribute between the teams. The teams take turns picking heroes: at first, the first team chooses a hero in its team, after that the second team chooses a hero and so on. Note that after a hero is chosen it becomes unavailable to both teams.\u003c/p\u003e\u003cp\u003eThe friends estimate the power of the $$$i$$$-th of the heroes as $$$p_i$$$. Each team wants to maximize the total power of its heroes. However, there is one exception: there are $$$m$$$ pairs of heroes that are especially strong against each other, so when any team chooses a hero from such a pair, the other team \u003cspan class\u003d\"tex-font-style-bf\"\u003emust\u003c/span\u003e choose the other one on its turn. Each hero is in at most one such pair.\u003c/p\u003e\u003cp\u003eThis is an interactive problem. You are to write a program that will optimally choose the heroes for one team, while the jury\u0027s program will play for the other team. Note that the jury\u0027s program may behave inefficiently, in this case you have to take the opportunity and still maximize the total power of your team. Formally, if you ever have chance to reach the total power of $$$q$$$ or greater regardless of jury\u0027s program choices, you must get $$$q$$$ or greater to pass a test.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\le n \\le 10^3$$$, $$$0 \\le m \\le n$$$)\u0026nbsp;— the number of players in one team and the number of special pairs of heroes.\u003c/p\u003e\u003cp\u003eThe second line contains $$$2n$$$ integers $$$p_1, p_2, \\ldots, p_{2n}$$$ ($$$1 \\le p_i \\le 10^3$$$)\u0026nbsp;— the powers of the heroes.\u003c/p\u003e\u003cp\u003eEach of the next $$$m$$$ lines contains two integer $$$a$$$ and $$$b$$$ ($$$1 \\le a, b \\le 2n$$$, $$$a \\ne b$$$)\u0026nbsp;— a pair of heroes that are especially strong against each other. It is guaranteed that each hero appears at most once in this list.\u003c/p\u003e\u003cp\u003eThe next line contains a single integer $$$t$$$ ($$$1 \\le t \\le 2$$$)\u0026nbsp;— the team you are to play for. If $$$t \u003d 1$$$, the first turn is yours, otherwise you have the second turn.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eHacks\u003c/span\u003e\u003c/p\u003e\u003cp\u003eIn order to hack, use the format described above with one additional line. In this line output $$$2n$$$ distinct integers from $$$1$$$ to $$$2n$$$\u0026nbsp;— the priority order for the jury\u0027s team. The jury\u0027s team will on each turn select the first possible hero from this list. Here possible means that it is not yet taken and does not contradict the rules about special pair of heroes.\u003c/p\u003e"}},{"title":"Interaction","value":{"format":"HTML","content":"\u003cp\u003eWhen it is your turn, print a single integer $$$x$$$ ($$$1 \\le x \\le 2n$$$)\u0026nbsp;— the index of the hero chosen by you. Note that you can\u0027t choose a hero previously chosen by either you of the other player, and you must follow the rules about special pairs of heroes.\u003c/p\u003e\u003cp\u003eWhen it is the other team\u0027s turn, read a line containing a single integer $$$x$$$ ($$$1 \\le x \\le 2n$$$)\u0026nbsp;— the index of the hero chosen by the other team. It is guaranteed that this index is not chosen before and that the other team also follows the rules about special pairs of heroes.\u003c/p\u003e\u003cp\u003eAfter the last turn you should terminate without printing anything.\u003c/p\u003e\u003cp\u003eAfter printing your choice do not forget to output end of line and flush the output. Otherwise you will get \u003cspan class\u003d\"tex-font-style-tt\"\u003eIdleness limit exceeded\u003c/span\u003e. To do this, use:\u003c/p\u003e\u003cul\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-tt\"\u003ecout.flush()\u003c/span\u003e in C++;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.flush()\u003c/span\u003e in Java;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush(output)\u003c/span\u003e in Pascal;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003estdout.flush()\u003c/span\u003e in Python;\u003c/li\u003e\u003cli\u003e see documentation for other languages.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eJury\u0027s answer $$$-1$$$ instead of a valid choice means that you made an invalid turn. Exit immediately after receiving $$$-1$$$ and you will see \u003cspan class\u003d\"tex-font-style-tt\"\u003eWrong answer\u003c/span\u003e verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3 1\n1 2 3 4 5 6\n2 6\n1\n\n2\n\n4\n\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n\n\n\n6\n\n5\n\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3 1\n1 2 3 4 5 6\n1 5\n2\n6\n\n1\n\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n\n\n\n\n5\n\n4\n\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example the first turn is yours. In example, you choose $$$6$$$, the other team is forced to reply with $$$2$$$. You choose $$$5$$$, the other team chooses $$$4$$$. Finally, you choose $$$3$$$ and the other team choose $$$1$$$.\u003c/p\u003e\u003cp\u003eIn the second example you have the second turn. The other team chooses $$$6$$$, you choose $$$5$$$, forcing the other team to choose $$$1$$$. Now you choose $$$4$$$, the other team chooses $$$3$$$ and you choose $$$2$$$.\u003c/p\u003e"}}]}