8663: Average Replacement

There are n people in a group and m pairs of friends among them. Currently, each person writes an integer on his hat. They plan to play the following game many times: everyone replaces his number on his hat with the average number of his number and all of his friends' numbers. That is, if before the game the person has a0 written on his hat and a total of k friends, each having number a1,...,ak, then after the game the number on his hat becomes 

（a0+⋯+ak  ）/ k+1

. Note that numbers may become non-integers.

It can be proved that by playing more and more games, each number converges to a certain value. Given the initial numbers written on the hats, your task is to calculate these values.

The first line contains the number of test cases T$(1\le T\le 100)$.

For each test case, the first line contains two integers n,m(1≤n,m≤105) .

The second line contains n integers a1,a2,⋯,an (1≤ai≤108) , indicating the number on each hat.

Each of the following $m$ lines contains two integers u,v $(1\le u,v\le n)$ , indicating a pair of friends.

It's guaranteed that there are no self-loop or multiple edges on the graph, and there are at most $20$ test cases such that n > 1000 or $m>1000$.