It is not an easy job to be a coach of a football team. (A
note to our American friends: football = soccer.) Especially if
you do not coach great teams like Ajax, Inter, Dynamo (ok, fill
in the name of your dream team), but only a mediocre one like
FC Dead Horse, playing in the second league. The season is
almost over, only a few matches are left to play. All of sudden
the team manager comes to you and tells you bad news: the main
sponsor of your club is not happy with your results and decided
to stop sponsoring your team, which probably means the end of
your club. The sponsor’s decision is final and there is no way
to change it unlessunless your team miraculously wins the
league.
The manager left you in deep thought. If you increase the
number of practices and offer players a generous bonus for each
match, you may be able to win all the remaining matches. Is
that enough? You also have to make sure that teams with many
points lose against teams with few points so that in the end,
your team will have more points than any other team. You know
some of the referees and can bribe them to manipulate the
result of each match. But first you need to figure out how to
manipulate the results and whether it is possible at all.
There are $N$ teams
numbered 1 through $N$,
your team has the number $N$. The current number of points of
each team and the list of remaining matches are given. Your
task is to find out whether it is possible to manipulate each
remaining match so that the team $N$ will finish with strictly more
points than any other team. If it is possible, give one
possible way to manipulate the results. In every match, the
winning team gets 2 points, the losing team gets 0. If the
match ends with a draw, both teams get 1 point.
Input
The input file consists of several blocks (at most 20). Each
block has the following form: The first line contains two
integers $1 \le N \le 100$
and $0 \le M \le 1000$.
The next line contains $N$
integers (each between $0$
and $200$, inclusively)
separated by spaces giving the current number of points of
teams $1, 2, \dots , N$
respectively. The following $M$ lines describe the remaining
matches. Each line corresponds to one match and contains two
numbers $a$ and
$b$ ($a \not= b$) identifying the teams
that will play in the given match. There is a blank line after
each block. The last block is followed by a $1$ on a separate line.
Output
For each block in the input file, output one possibility how
to manipulate the remaining matches. Output $M$ numbers separated by spaces or end
of line characters; the $i$th number will represent the
result of the $i$th
match. Indicate the victory of the first team by 0, a draw by
1, and the victory of the second team by 2. If it is not
possible to manipulate the remaining matches so that the team
$N$ would win the league,
output a single line containing the word ‘NO’.
Sample Input 1 
Sample Output 1 
5 8
2 1 0 0 1
1 2
3 4
2 3
4 5
3 1
2 4
1 4
3 5
5 4
4 4 1 0 3
1 3
2 3
3 4
4 5
1

2 0 2 2 2 1 2 2
NO
