Count Distinct Managers

In a company, every employee (except the top manager) directly reports to one manager. The company structure is given as a rooted tree with employee 1 as the top manager. Given the number of employees and direct reporting relationships, your task is to determine, for each employee, the number of distinct managers that exist above him/her in the company hierarchy.

More formally, you are given an integer \( n \) (the number of employees, numbered from 1 to \( n \)) and an integer \( m \) representing the number of direct reporting relationships. Each of the following \( m \) lines contains two integers \( u \) and \( v \), meaning that employee \( u \) is the direct manager of employee \( v \). It is guaranteed that the relationships form a tree with employee 1 being the root. The number of distinct managers for an employee is defined as the distance in the tree from employee 1 to that employee.

Output the number of managers for each employee in order from employee 1 to employee \( n \).

Note: Use \( \LaTeX \) syntax for any formulas, e.g., \( n,\ m,\ u,\ v \).

inputFormat

The first line contains an integer \( n \) (the number of employees).

The second line contains an integer \( m \) (the number of direct reporting relationships).

Each of the next \( m \) lines contains two integers \( u \) and \( v \), indicating that employee \( u \) is the direct manager of employee \( v \).

You can assume that \( n \geq 1 \) and the relationships form a tree with employee 1 as the root.

outputFormat

Print a single line containing \( n \) integers separated by spaces. The \( i \)-th integer represents the number of distinct managers of employee \( i \) (which is equivalent to the distance from employee 1 to employee \( i \) in the tree). For employee 1, output 0.

## sample

6
5
1 2
1 3
2 4
2 5
3 6

0 1 1 2 2 2

</p>