A2231 · Monkey King · GESP考级

题目描述

曾经在一个森林中居住着 $N$ 只好斗的猴子。在最初他们我行我素，互不认识。但是猴子们不能避免争吵，且两只猴子只会在不认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。 假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如 $10$ 会减少到 $5$，而 $5$ 会减少到 $2$，即向下取整）。 我们也假设每只猴子都认识它自己（是自己的朋友）。即当他是他朋友中最强壮的，他自己就会去决斗。

有多组数据，每一组数据有两部分。 第一部分：第一行包含一个整数 $N$ 表示猴子的数量。后为 $N$ 行，每行一个数字为第 $i$ 只猴子的强壮值 $s_{i}$。 第二部分：第一行包含一个整数 $M$ 表示发生了 $M$ 次冲突。后为 $M$ 行，每行两个整数 $x$ 和 $y$，表示第 $x$ 只猴子和第 $y$ 只猴子之间发生了冲突。

对于每次冲突，如果两只猴子认识对方，输出 -1，否则输出决斗后他们朋友中最强壮的猴子的强壮值。 说明/提示 $N,M\leq 100000$，$s_{i}\leq 32768$

输入 #1

输出 #1