Identity

You are given a tree with $N$ vertices numbered from $1$ through $N$. Every edge has weight $0$ or $1$.

The tree distance $d_T(u,v)$ between two vertices is the sum of the edge weights on their unique path.

Place every vertex $v$ at an integer coordinate $x_v$ on a line. Every pair of distinct vertices $u,v$ must satisfy both conditions below.

• $x_u\neq x_v$.
• $\mathrm{\mid }{x}_u-x_v\mathrm{\mid }\ge d_T(u,$.

In particular, vertices at tree distance $0$ must still be placed at distinct coordinates.

The length of a placement is

Find the minimum possible value of $L$.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the minimum possible length of a valid placement.

• $1\leq T\leq200\,000$.
• $1\leq N\leq200\,000$.
• $1\le {}_{}$.