All Submissions

Problem Description
Bored of coding, ACM founded its own football club "ACM United" and made you the coach. But it is not a simple task to be the coach of a new and inexperienced football team. The season is almost over and only a few matches are left to be played. The only sponsor of your club, 'Google' is not happy with your results and decides to stop sponsoring unless your team wins the league. No sponsor probably means the end of your club and you should avoid this if possible.
There are a total of N teams numbered from 1 to N. ACM United has the number N. The current score of each team is given and there are a total of M matches left to be played. You are also given the fixtures of the remaining M matches, which can be played in any order.
The scoring of points in a match is done as follows:
  • The winner gets 2 points and the loser gets 0 point.
  • If the match ends in a draw, both the teams get 1 point each.

Out of the remaining matches, you need to make sure that teams with higher scores lose against teams with lower scores so that in the end, ACM United has the highest score. All the referees can be bribed and you can manipulate the result of any match. Your task is to find out whether it is possible to manipulate the results of the remaining matches (by bribing, of course!) so that ACM United finishes with more points than any other team.

Input Specification
Input consists of several test cases.
The first line of each test case contains two integers N and M. The second line contains N integers giving the current score of teams 1,2,3,...,N respectively. This is followed by M lines, each line containing two integers X and Y. Each of these M lines represents a remaining match between the teams numbered X and Y.
The last test case is followed by -1.

Output Specification
For each test case, print "ACM United Wins" if it is possible to manipulate the result so that ACM United wins the league, otherwise print "ACM United Loses". ACM United wins only if its score is strictly greater than all the other teams, otherwise it loses.
Each output should be followed by a new line.

  • Number of test cases <= 30
  • All the given numbers fit in 32 bit integer.
  • 1 <= N <= 100
  • 0 <= M <= 1000
  • 1 <= X,Y <= N
  • X != Y

Sample Input

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

3 2
2 2 2
1 3
1 2

3 3
2 2 2
1 3
1 2
1 2

4 3
9 2 3 4
1 4
3 4
2 3


Sample Output

ACM United Wins
ACM United Wins
ACM United Loses
ACM United Loses

Problem Setter: Rohan Laishram

Languages: C,C++,Java

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes


Login to post clarification.

No Clarifications.


Mode Judge



Overall Rankings