题目描述

会议室中，所有人望着PPT上的图片，一张张脸上写满了难以置信的表情。那是一张错中复杂的图片，密密麻麻的线条震撼着眼球。“这是我们对敌方间谍的调查结果，现在他们的情报网络已经呈现在你们的面前”国安部长淡淡的说，“我需要在场的你们对这张图进行分析，来确定怎样对敌方施以打击。”

Marvolo突然站起来喊道：“这情报网其实是一棵树！而我擅长树!”。Mike在愣了片刻后也恍然大悟道：“我明白了！如果把这张图转化一下的话，这不就是……”

我们得到了一个敌方的间谍情报图，每个敌方间谍都有其相对应的重要程度。在情报图上，可以知道所有间谍的情报流向，也就是形如间谍A向间谍B传递情报的格式(所有的情报流向方向均为单向，不保证没有环，保证无自环)。现在在这个图上有$N$个间谍，$M$条情报传递流向。一个间谍如果从能收到情报到无法收到情报的状态，则称该间谍静默。定义一个间谍的毁灭度为如果消灭该间谍(也就是说他无法接受和传递情报)，所有因为该间谍被消灭而静默的间谍的重要度之和。现在请求出所有间谍的毁灭度(不明白题意看数据)。

输入格式

第一行为两个整数$N,M$，表示间谍数量和情报流向总数。

接下来一行有$N$个整数，表示每个间谍的重要度。

接下来$M$行，每行两个整数$A,B$，表示间谍$A$向间谍$B$传递情报。

输出格式

共$N$行，表示每个间谍的毁灭度。

样例输入 1

ex_tree1.in

3 3
1 2 3
1 2
2 3
1 3

样例输出 1

ex_tree1.ans

5
0
0

样例解释

如图(假装有图，逃)，1号向2,3号间谍传递情报，2号向3号传递情报。如果1号被消灭，2,3号都会静默，所以毁灭度为5.同理，2号的毁灭度为0，因为他被消灭后，3号仍能从1号那里接收消息。3号的毁灭度为0，他没有出边。

样例 2

见样例数据下载。

数据范围

1号间谍为情报源头

对于所有的 $25$ 个测试点，保证：

• 从 $1$ 号间谍发出的情报可以传达到所有人手上。
• $1$ 号点的入度为 $0$。
• 所有的间谍重要度不超过 $2^{31} - 1$。

我们定义性质 $t$ 为：任何一个间谍的情报不可能通过其他间谍，又传回到自己手上。

各个测试点的详细信息如下表所示：

测试点编号	$N$	$M$	性质 $t$
$1$	$\leq 5$	$=N-1$	√
$2$
$3$		$\leq 10$
$4$		$\leq 20$	×
$5$
$6$	$\leq 20$	$\leq 2,000$	√
$7$	$\leq 40$		×
$8$	$\leq 80$		√
$9$	$\leq 100$		×
$10$	$\leq 200$		√
$11$	$\leq 500$	$=N-1$
$12$	$\leq 1,000$	$=N$	×
$13$	$\leq 5,000$	$\leq 100,000$
$14$	$\leq 10,000$		√
$15$			×
$16$	$\leq 100,000$	$=N-1$	√
$17$
$18$		$=N$	×
$19$		$\leq 1,000,000$	√
$20$
$21$			×
$22$
$23$
$24$
$25$

赛后本题将开放 Hack。

时间限制：1s

空间限制：256M

样例数据下载