2013年7月18日 星期四

11690 - Money Matters

Problem B - Money Matters

Time limit: X seconds

這一個悲傷的故事該從一群朋友說起,他們一起去風景勝地莫法尼亞(虛構的國家)旅行。在旅行途中,發生了一些令人毛骨悚然的事件,在旅行的最後一晚,居然有朋友說出「我不想再見到妳了!」約略地計算可能說了高達五千萬次。

當回到故鄉斯堪地納維亞(北歐)時,他們發現他們沒有均勻地平攤旅行花費,有些人甚至多付了數千克朗(一種貨幣單位),現在問題是想要平攤這些花費,然而因為關係分裂,導至有些人不想跟其他人說話,更別說要談論分錢的問題。


你現在要幫助他們,所以你要得知每個人欠了多少、多付了多少,以及誰與誰仍是朋友關係,根據這些訊息,問是否有可能將旅費平攤,錢只能藉由仍是朋友關係間互相傳遞。

Input

第一行 有一個整數 N (N <= 20),表示接下來有多少測資組。

每組測資第一行有兩個整數 n (2 ≤ n ≤ 10000),  m (0 ≤ m ≤ 50000),分別表示有多少為朋友及朋友關係的數量。接下來會有 n 行,第 i (0 <= i < n)行有一個整數 o (-10000 ≤ o ≤ 10000) 表示第 i 個人的欠款(o < 0) 或者多付了多少錢

接下來會有 m,每行上有兩個整數 x, y (0 ≤ x < y ≤ n-1),表示 x, y 間仍保有朋友關係。

Output

對於每組測資,輸出是否有可能平攤旅費  POSSIBLE or IMPOSSIBLE.

Sample Input

2
5 3
100
-75
-25
-42
42
0 1
1 2
3 4
4 2
15
20
-10
-25
0 2
1 3