You are given a tree. Simple path of length $$m$$ is a sequence of vertices $$v_1, v_2, \dots, v_m$$ such that
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.
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 $$n$$ lines. $$i$$-th line must contain two integers -- length of the longest simple path containing vertex $$i$$ and number of such paths.
$$1 \leqslant n \leqslant 300,000.$$
Additionally $$n \leqslant 3,000$$.
No additional constraints.
Longest paths going through vertex $$1$$: $$(1, 2, 3)$$, $$(1, 2, 4)$$.
Longest paths going through vertex $$2$$: $$(1, 2, 3)$$, $$(1, 2, 4)$$, $$(3, 2, 4)$$.
Cases of vertices $$3$$ and $$4$$ are similar to vertex $$1$$.