Server Time: Fri Oct 30, 2020 4:47 am
Welcome ( logout
B - Equalizing Money
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

There are n people in a certain village. Each of them contains some amount of money. One day a wise person told them to distribute the money such that everyone has equal amount of money. If they can do so, they will be favored by their fortunes.

You are given the information about the money of each person and some relations. Each relation is of the form u v. That means person u and v are capable of making money transactions. They are allowed to use transactions any number of times but they have to do integer transactions only.

Now your task is to answer whether they can redistribute the money such that each of them contains exactly same of money.


Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (2 ≤ n ≤ 1000) and m (0 ≤ m ≤ 10000) where m denotes the number of relations. The next line contains n space separated integers ranging from 0 to 1000. The ith integer of this line denotes the money for the ith person. Each of the next m lines contains two integers u v (1 ≤ u, v ≤ n, u ≠ v) meaning that person u and v can make transactions. No relation is reported more than once.


For each case, print the case number and 'Yes' if they can equalize their money or 'No' otherwise.

Sample Input

Output for Sample Input


5 4

1 0 1 1 2

1 2

2 3

3 4

4 5

2 1

5 10

1 2

4 2

1 1 0 2

1 2

2 3

Case 1: Yes

Case 2: No

Case 3: No


Dataset is huge, use faster I/O methods.

Problem Setter: Jane Alam Jan
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan