DAGCNT2 - Counting in a DAG

You are given a weighted DAG. For each vertex, calculate the sum of the weights of the vertices within its reach (including itself).

Input

The first line contains an integer T, denoting the number of test cases.

For each test case, the first line contains two positive integers n and m, denoting the number of vertices and the number of edges in the DAG.

The second line contains n positive integers w1..wn, denoting the weights of vertices.

The next m lines contain two positive integers u,v, denoting an edge from u to v.

Output

For each test case, print a line consisting of n numbers, denoting the sum for each vertex.

Example

Input:
2
4 3
510 713 383 990
4 1
4 2
2 1
4 4
450 379 230 520
3 4
2 4
2 3
2 4

Output:
510 1223 383 2213
450 1129 750 520

Constraints

Input Set 1: numberOfTestCases <= 40, n <= 100, m <= 10000

Input Set 2: numberOfTestCases <= 2, n <= 1000, m <= 500000

Input Set 3: numberOfTestCases <= 2, n <= 20000, m <= 500000

The weights are no more than 1000


Added by:Lox
Date:2009-09-30
Time limit:0.100s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL NODEJS PERL6 VB.NET
Resource:Own problem

hide comments
2021-06-19 11:53:51
can we solve this problem without bitset?
2020-08-27 18:06:14
use bitset, it will reduce the time complexity by 32.

Last edit: 2020-08-27 18:23:54
2020-07-22 14:47:22
2nd test case is wrong
2016-08-10 21:38:15 Shaka Shadows
@Rohit Agarwal, you can mail me if you still need some help in this one.
2015-10-23 19:36:37 Repon Kumar Roy
After changing time limit, some previous AC solutions get TLE.
2015-02-06 18:43:42 Rohit Agarwal
Can anyone please tell me how exactly topological sort helps to find the solution for this problem?
2014-06-29 06:31:52 jolt
could it be passed by using "bitset structure" defined by us? I always got a TLE.
2009-10-10 20:13:03 Josef Ziegler
cin and cout is quite slow - try printf and scanf

Last edit: 2009-10-11 12:25:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.