2691. Money Matters

单点时限: 6.0 sec

内存限制: 256 MB

Our sad tale begins with a tight clique of friends. Together they went on a trip to the

picturesque country of Molvania. During their stay, various events which are too horrible

to mention occurred. The net result was that the last evening of the trip ended with a

momentous exchange of “I never want to see you again!”s. A quick calculation tells you

it may have been said almost 50 million times!

Back home in Scandinavia, our group of ex-friends realize that they haven’t split the

costs incurred during the trip evenly. Some people may be out several thousand crowns.

Settling the debts turns out to be a bit more problematic than it ought to be, as many in

the group no longer wish to speak to one another, and even less to give each other money.

Naturally, you want to help out, so you ask each person to tell you how much money

she owes or is owed, and whom she is still friends with. Given this information, you’re

sure you can figure out if it’s possible for everyone to get even, and with money only being

given between persons who are still friends.

输入格式

The first line contains two integers, n (2 <= n <= 10000), and m (0 <= m <= 50000), the

number of friends and the number of remaining friendships. Then n lines follow, each

containing an integer o (-10000 <= o <= 10000) indicating how much each person owes

(or is owed if o < 0). The sum of these values is zero. After this comes m lines giving

the remaining friendships, each line containing two integers x, y (0 <= x < y <= n - 1)

indicating that persons x and y are still friends.

输出格式

Your output should consist of a single line saying “POSSIBLE” or “IMPOSSIBLE”.

样例

Input
5 3
100
-75
-25
-42
42
0 1
1 2
3 4
4 2
15
20
-10
-25
0 2
1 3
Output
POSSIBLE
IMPOSSIBLE

38 人解决,57 人已尝试。

51 份提交通过,共有 118 份提交。

4.4 EMB 奖励。

创建: 12 年,2 月前.

修改: 4 年,3 月前.

最后提交: 1 年前.

来源: NCPC 2009

题目标签
dsu