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 w_{1}..w_{n}, 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
hide comments
hoang2004:
20210619 11:53:51
can we solve this problem without bitset? 

hetp111:
20200827 18:06:14
use bitset, it will reduce the time complexity by 32. Last edit: 20200827 18:23:54 

subhram79788:
20200722 14:47:22
2nd test case is wrong


Shaka Shadows:
20160810 21:38:15
@Rohit Agarwal, you can mail me if you still need some help in this one. 

Repon Kumar Roy:
20151023 19:36:37
After changing time limit, some previous AC solutions get TLE. 

Rohit Agarwal:
20150206 18:43:42
Can anyone please tell me how exactly topological sort helps to find the solution for this problem? 

jolt:
20140629 06:31:52
could it be passed by using "bitset structure" defined by us? I always got a TLE. 

Josef Ziegler:
20091010 20:13:03
cin and cout is quite slow  try printf and scanf Last edit: 20091011 12:25:24 
Added by:  Lox 
Date:  20090930 
Time limit:  0.100s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL NODEJS PERL6 VB.NET 
Resource:  Own problem 