Farthest Node

mediumGraphDFSdfs-diameter of tree variant

You are given a tree consisting of $$$n$$$ nodes.

Find out for each node the distance to the farthest node in the tree.

Input Format:

The first line contains a single integer $$$n$$$ $$$(2 \le n \le 2\cdot 10^5)$$$ — the number of nodes in the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n)$$$, representing an undirected edge between node $$$u$$$ and node $$$v$$$.

It is guaranteed that the given edges form a tree.

Output Format:

Print N integers: for each node, the distance to the farthest node.

Examples:

Example 1:

Input:

3
1 2
2 3

Output:

2 1 2

Example 2:

Input:

5
1 2
1 3
3 4
4 5

Output:

3 4 2 3 4

Note:

Code

Loading Editor...