暂无测试数据。

Background

___出了一道树上最短路入门题

给定一棵 \(N\) 个点的树，和一个长为 \(M\) 的序列 \(p\)，求依次走过 \(p\) 中的点，路径总长是多少。保证 \(p\) 中没有相同的点，且 \(\forall 1\leq i<M\)，\(p_i\) 与 \(p_{i+1}\) 的路径上不含 \(p\) 中除 \(p_i,p_{i+1}\) 以外的点。

Description

___的标算是使用了 \(O(n)-O(1)\) RMQ 的优秀做法，他需要卡掉 \(O(m\log n)\) 的暴力。但是他发现，由于限制的原因，\(M\) 可能远远达不到 \(N\) 的级别。所以对于给定的一棵树，为了卡掉暴力，他需要求出最长的 \(M\) 能有多长。

Input Format

第一行一个正整数 \(N\)。

接下来 \(N\) 行，每行两个正整数 \(u_i,v_i\) 表示树的一条边。

Output Format

输出最大的 \(M\)。

Sample 1

Input

Output

explanation

Sample 2

Input

Output

explanation

502 - Bad Gateway

Limitation

对于所有数据，\(1\leq N,M,Q\leq 10^5\)，对于任意时刻 \(1\leq a_i,b_i\leq 10^5\)。

Subtask 1[5 pts]

不存在操作 \(2\)。

Subtask 2[5 pts]

\(N,M,Q,a_i,b_i\leq 100\)。

Subtask 3[10 pts]

\(N,M,Q,a_i,b_i\leq 1000\)。

Subtask 4[25 pts]

\(N,a_i,b_i\leq 1000\)。

Subtask 5[15 pts]

不存在操作 \(1\)。

Subtask 6[40 pts]

无特殊限制。