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 i^{th} integer of this line denotes the money for the i^{th} 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 |
3 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.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |