Algorithms and Data Structures

# Find the Diameter of a Tree

You are given a tree with `v` vertices and your task is to find the diameter of the tree. The diameter is the length of the path between the two furthermost vertices.

#### Input

The first line of the input contains a single integer `v` (1 ≤ v ≤ 100 000).
The following `v-1` lines contain pairs of integers `v1`, `v2` (1 ≤ v1, v2 ≤ v) which means that the vertex `v1` is connected to the vertex `v2` and vice versa.

#### Output

The program should print the diameter of the given tree.

#### Examples

 Input Output 3 1 2 1 3 2 5 1 2 1 3 3 4 3 5 3
Hint 1
You can perform DFS multiple times from different sources
Hint 2
You can perform DFS starting from node 1 and find the furthermost vertex (as this is a tree, meaning there are no cycles, we can do that without BFS).
Then start a DFS from the found furthermost vertex and find the farthest vertex from that one.

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB