Given a tree of $n$ vertices rooted at $1$. For each vertex $i$, count the number of vertices in the subtree rooted at $i$.
### Input
- The first line contains an integer $n$.
- The next $n - 1$ lines, each line contains two integer $u,v$,, there is an edge between $u$ and $v$.
### Output
- Print $n$ integers, the $i^{th}$ integer is the number of vertices in the subtree rooted at $i$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le u, v \le n$.
### Example
Input:
```
5
1 2
1 3
3 4
3 5
```
Output:
```
5 1 3 1 1
```
