Chuan the Shen Qi (神奇) finds the general problem too easy. Hence he has decided to try out gen_ex, which is this problem! In this problem, the second most powerful general of a faction can overthrow the most powerful one by means of a revolution!
The first line of input consists of two integers N and M (1 ≤ N, M ≤ 600,000).
The next N lines of input each contains one integer Pi, representing the power level of the i-th faction. No two factions have the same power level.
The next M lines contain two integers a and b each.
If a = -1, that means that the general with greatest power level in the faction containing general b is overthrown and banished from the faction.
Otherwise, generals a and b have started a battle, which their factions will soon join.
If any of the queried generals have already been overthrown before, print out "-1".
Otherwise, for each revolution, print out the new power level of the faction. If there is only one general in the faction, he cannot be overthrown so print out -1 instead. For each battle, print out one integer, indicating the faction which has won the battle. If two generals from the same faction fight, it is only considered an internal misunderstanding, and one should print out -1 instead.
Sample Input 1
Sample Output 1