Consider a tree with $n$ vertices, where vertex 1 serves as the root. Our goal is to determine the depth of each vertex, which is defined as the count of edges along the path from the vertex to the root.
### 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 depth of vertex $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:
```
0 1 1 2 2
```
