The Flee Plan of Groundhog
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Groundhog was especially careful after the outbreak,so he put on his mask in the  bedroom early,and then walked on the way to the  dormitory to play with Orange. There are  dormitories in ZLZX, which are connected by corridors. Each dormitory can be reached to each other.The length of each corridor is .The walking speed of Groundhog is .

At that moment the bad news came: After Groundhog set out for  seconds,Orange took his temperature, and it turned out to be 41℃ !!! In addition to grief and indignation, Orange decided to run to Groundhog, to tell him the news at the speed of  .

Groundhog had to run, of course, but he was running too slow at  . As he ran, he had an idea: if he ran with the best strategy, how soon would Orange catch up  with him? Define that every second Groundhog moves and then Orange moves again. Groundhog can choose to stay put.

Groundhog would have solved that, of course, but he is running away now, so he give it to you, the smartest one.

输入描述:

The first line contains two integers 。
The next  lines，each line contains two integers , indicating there is a corridor between the   dormitory and the  dormitory.

输出描述:

An integer, indicating the latest time for Orange to catch Groundhog.
示例1

输入

复制 
7 2
1 2
2 5
5 7
5 6
3 6
3 4

输出

复制 
1

说明

After {t} seconds, Groundhog is in the 5^{th} dormitory and Orange is in the 7^{th} dormitory.At this point, the best way for Groundhog is to goto the 2^{nd} dormitory or the 6^{th} dormitory.But wherever he goes, he will be immediately caught by Orange.

备注:

.