You are given a tree. Simple path of length m is a sequence of vertices $v_1, v_2, \dots, v_m$ such that

• All $v_i$ are distinct.
• $v_i$ and $v_{i+1}$ are connected by edge for $1 \leqslant i \leqslant m - 1$.

For each vertex find length of longest simple path that goes through this vertex. Also count number of this paths. Two paths considered distinct if set of vertices of this paths differ.

Input Format:
First line of input contains single positive integer n -- number of vertices of the tree.
Next $n - 1$ lines contains pairs space-separated integers $u_i, v_i$ -- edges of the tree.

Output Format:
Output n lines. i-th line must contain two integers -- length of the longest simple path containing vertex i and number of such paths.

Constraints:
$1 \leqslant n \leqslant 300,000.$

Scoring:
50 points
Additionally $n \leqslant 3,000$.
50 points
No additional constraints.