p03898 CODE FESTIVAL 2016 Relay (Parallel) - Problem on Tree
There is a tree with N vertices, numbered 1 through N.

The i-th of the N-1 edges connects the vertices p_i and q_i.

Among the sequences of distinct vertices v_1, v_2, ..., v_M that satisfy the following condition, find the maximum value of M.

* For every 1 \leq i < M, the path connecting the vertices v_i and v_{i+1} do not contain any vertex in v, except for v_i and v_{i+1}.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq p_i, q_i \leq N
* The given graph is a tree.

Input

The input is given from Standard Input in the following format:


N
p_1 q_1
p_2 q_2
:
p_{N-1} q_{N-1}


Output

Print the maximum value of M, the number of elements, among the sequences of vertices that satisfy the condition.

Examples

Input

4
1 2
2 3
2 4


Output

3


Input

10
7 9
1 2
6 4
8 1
3 7
6 5
2 10
9 6
2 6


Output

8
```python
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

"""
・次数3以上の点は使わないとしてよい
・次数1の点は全て回収できる。次数2の点を、パスとなる形で回収する。
"""

N = int(readline())
PQ = [tuple(int(x)-1 for x in line.split()) for line in readlines()]

graph = [[] for _ in range(N)]
for p,q in PQ:
    graph[p].append(q)
    graph[q].append(p)    

deg = [len(x) for x in graph]

cnt_deg1 = sum(x==1 for x in deg)

deg2_path = 0

def dfs(x,parent):
    global deg2_path
    # 部分木で完結する場合、しない場合
    arr = [dfs(y,x) for y in graph[x] if y != parent]
    if len(arr) == 0:
        return 0
    if len(arr) == 1:
        return arr[0] + (deg[x] == 2)
    arr.sort()
    deg2_path = max(deg2_path, arr[-1] + arr[-2] + (deg[x]==2))
    return arr[-1] + (deg[x] == 2)

dfs(0,-1)
answer = cnt_deg1 + deg2_path
print(answer)
```