oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

general Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

general.html

In a faraway warring country, there are N generals from different factions engaged in numerous battles. Each faction has a power from 1 to N, such that a faction with higher power always defeats a faction with lower power. Indeed, after a faction is defeated by another, all its members are absorbed into the winning faction. The power of a faction is the maximum of the powers of all its members.

Initially, all generals are in individual factions. You are given the details of M battles between two generals. However, since generals seem to be a very closely-knit bunch, the full strength of the faction will aid in every battle any of its members undertakes. Given the details of these battles, we wish to find out the victorious faction in each battle

Input

The first line of input consists of two integers N and M (1 ≤ N, M ≤ 100,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, indicating that generals a and b have started a battle, which their factions will soon join

Output

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

5 4
1
2
3
4
5
1 5
1 2
1 2
3 4

Sample Output 1

5
5
-1
4

Tags

Union Find Disjoint Set

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o general -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.