When WeChat first introduced the function of "counting steps",people began to compete with each other.

The function of  "counting steps" involves two parts:

1. Count the steps he/she walks today.
2. Show the one who walks most today in he/she's friend list, we may call the one a "walking champion".

In each minute, he/she may walk more, so the "walking champion" in he/she's friend list changes dynamically.

In this problem, There are  people in total, numbered from  to . Friendships are described as a undirected graph with  vertices and  edges.

We divide a day into  time units. In each time unit, only one person walks several steps. One becomes "walking champion" in he/she's friend list, if and only if he/she walks at least  step and the number of his walking steps is strictly greater than anyone else's in he/she's friend list.

You are given the graph, who walks and how many steps he/she walks in each time unit. 

For each person, you are asked to calculate the total number of time units that he/she becomes a "walking champion" in he/she's friend list.

To be more specific, if one became a champion after time unit, and ended after time unit (if he/she keeps a championship until the end, then ), then we say he/she becomes a champion for  time unit(s).

输入描述:

Input consists of  lines.

The firsts line contains  — the number of people, the number of friendships, the number of time units.

Then  lines ,each line contains two integer  ,denoting the  friendship.

Then  lines, each line contains two integer , denoting that the  person walks  steps during  time unit.

输出描述:

Output  lines,  line contains the total number of time units that  person becomes a "walking champion" in  he/she's friend list.

10 10 10
5 7
3 7
7 9
6 9
1 5
1 4
5 6
7 8
4 6
3 6
3 201
5 6266
2 2593
1 3241
5 1028
2 6040
4 1025
1 5563
7 3741
6 6129

2
7
8
0
6
0
0
0
0
0

备注:

.
It's guaranteed that , any  does not appear twice in the graph and at any time nobody walks more than  steps.