题目描述

Little m is a famous warrior who kills the monsters. He lives in a small country which is always disturbed by monsters. When he is not busy, he just guards the castle of the king of the country and when there are monsters coming, he immediately sets off from the castle and goes to the battleground all over the border lines of the country.

As he is a brave and experienced warrior, he will kill the monsters without even being serious. So, after killing the monsters, he will go back to the castle to do the guarding.

The country is consisting of many villages, two villages is connected by one road. And the castle is in the middle of the country.

When little m is on his way back, some villagers will give him some rewards for killing the monsters and saving the people, but some corrupt local governors will ask him rewards as they have let him passing the local village and have cost many things to kill the monsters.

Little m is a man who doesn't like to have too many wealth. So if the villagers give him something he doesn't have at that time, he will accept it, but if he has got that, he will not accept the same thing.

And if the local governors ask something little m has, little m will give that to the governor, but if little m hasn't got that yet, he will give the governor nothing.

The villages also have levels, the village who are more remote from the castle has lower level, to get back to the castle, little m must kill all the monsters from lower level village.

For example: Suppose that we are at village indexed 1, if we want to go back ,we must kill all the monsters at border lines in villages indexed 2 and 3.

In order to have a list of the rewards, little m comes to you to help him. So, you need to print the list on the way back, which is at each village how many different kinds of things little m has got?

输入格式

The first line of the input contains one positive integer $n (1\\le n \\le50000)$ indicates the number of the villages.

Then next $n-1$ lines each line contains two positive integers, $x_i,y_i (1\\le x_i,y_i \\le n)$ indicating there's one road between $x_i$ and $y_i$.

Then comes from the rewards of each village, each reward is a word consisting of only lowercase English letters which at most have 10 each.

If it is the governor asking for reward, the word will start with a $-$

It is guaranteed that the castle is always indexed 1 and all villages and castle are connected by each other.

输出格式

Print one line $n$ numbers, the list of the rewards on the way back, which is at each village how many different kinds of things little m has got.

样例

5 
1 2 
1 3 
2 4 
2 5 
apple -apple bread apple banana

3 1 1 1 1

4 
1 2 
3 2 
4 3 
-apple apple apple apple

0 1 1 1

提示

The first sample is above. If we suppose little m will go to village 2,4,5 first, so at village 4 he will get one apple, and at village 5 he will get one banana, but at village 2 he will lose his apple.