Marisa lives in the Magic Forest, which can be visualized as a tree with $n$ vertices. Her house is located at vertex $1$. Over the next $n$ days, Marisa plans to visit a different vertex each day to harvest mushrooms. Specifically, on day $i$, she will travel to vertex $A_i$. During her journey to harvest mushrooms, Marisa wants to keep track of the number of vertices where she has already collected mushrooms. Can you assist her in counting this number?
### Input
- The first line contains two integer $n$.
- The next $n - 1$ lines, each line contains two integer $u,v$, there is a path between $u$ and $v$.
- The next line contains $n$ integer $A_i$. It is guaranteed that the sequence $A$ represents a permutation of integers ranging from $1$ to $n$.
### Output
- Print $n$ integers, the $i^{th}$ integer is the number of already hervested vertices on her journey on day $i$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le u,v \le n$.
### Example
Input:
```
5
1 4
5 4
1 3
2 4
4 2 1 5 3
```
Output:
```
0
1
0
2
1
```
