CF1056C.Pick Heroes

Don't you tell me what you think that I can be

If you say that Arkady is a bit old-fashioned playing checkers, you won't be right. There is also a modern computer game Arkady and his friends are keen on. We won't 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.

There 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.

The 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 must choose the other one on its turn. Each hero is in at most one such pair.

This is an interactive problem. You are to write a program that will optimally choose the heroes for one team, while the jury's program will play for the other team. Note that the jury's 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's program choices, you must get $q$ or greater to pass a test.

别告诉我你认为我能做到什么

如果你说阿卡季玩跳棋有点过时，那你就错了。他和朋友们还热衷于一款现代电脑游戏。我们不会讨论它的规则，本题中唯一重要的是：每位玩家在游戏开始时必须选择一个独一无二的英雄。

共有 $2$ 支队伍，每支队伍各有 $n$ 名玩家，以及 $2n$ 个可供分配的英雄。两支队伍轮流选择英雄：首先由第一支队伍为其队伍选择一名英雄，然后第二支队伍选择一名英雄，依此类推。注意：一旦某位英雄被选中，该英雄即对双方队伍均不可用。

朋友们将第 $i$ 位英雄的力量值估计为 $p_i$。每支队伍都希望最大化其队伍所选英雄的总力量值。然而，存在一种例外情况：有 $m$ 对英雄彼此之间具有特别强的克制关系；因此，当任意一支队伍选择了这样一对中的某个英雄时，另一支队伍必须在下一轮选择该对中的另一个英雄。每位英雄至多属于这样的一对。

本题为交互式问题。你需要编写一个程序，为其中一支队伍最优地选择英雄，而评测系统的程序将为另一支队伍进行操作。注意：评测系统的程序可能表现得并不高效；此时，你必须抓住机会，依然尽可能最大化己方队伍的总力量值。形式化地说：若在任何时刻，无论评测系统程序如何选择，你都有机会使己方队伍的总力量值达到或超过 $q$，那么你必须实际达成至少 $q$ 的总力量值，才能通过该测试用例。

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^3$, $0 \le m \le n$) — the number of players in one team and the number of special pairs of heroes.

The second line contains $2n$ integers $p_1, p_2, \ldots, p_{2n}$ ($1 \le p_i \le 10^3$) — the powers of the heroes.

Each of the next $m$ lines contains two integer $a$ and $b$ ($1 \le a, b \le 2n$, $a \ne b$) — a pair of heroes that are especially strong against each other. It is guaranteed that each hero appears at most once in this list.

The next line contains a single integer $t$ ($1 \le t \le 2$) — the team you are to play for. If $t = 1$, the first turn is yours, otherwise you have the second turn.

Hacks

In order to hack, use the format described above with one additional line. In this line output $2n$ distinct integers from $1$ to $2n$ — the priority order for the jury's team. The jury's 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.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^3$，$0 \le m \le n$）—— 分别表示每支队伍的玩家数量以及特殊英雄对的数量。

第二行包含 $2n$ 个整数 $p_1, p_2, \ldots, p_{2n}$（$1 \le p_i \le 10^3$）—— 表示各位英雄的力量值。

接下来的 $m$ 行中，每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le 2n$，$a \ne b$）—— 表示一对彼此特别克制的英雄。保证该列表中每个英雄至多出现一次。

下一行包含一个整数 $t$（$1 \le t \le 2$）—— 表示你所代表的队伍。若 $t = 1$，则由你先手；否则你后手。

Hack 方法

为了进行 Hack，请使用上述格式，并额外添加一行。该行需输出 $2n$ 个互不相同的、取值范围为 $1$ 到 $2n$ 的整数——表示裁判方队伍的优先选取顺序。裁判方队伍在每次轮到其行动时，将从该列表中选择第一个“可行”的英雄。“可行”意味着该英雄尚未被选中，且其选取不违反关于特殊英雄对的规则。

In 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$.

In 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$.

在第一个例子中，由你先手。例如，你选择 $6$，对方队伍被迫回应 $2$；接着你选择 $5$，对方队伍选择 $4$；最后你选择 $3$，对方队伍选择 $1$。

在第二个例子中，你后手。对方队伍先选择 $6$，你选择 $5$，迫使对方队伍选择 $1$；接着你选择 $4$，对方队伍选择 $3$，最后你选择 $2$。