Statement

The monkeys at the zoo of Pordenone have N trees (numbered from 0 to N-1) to play on, with M suspended bridges connecting some pairs of them. The bridges are numbered from 0 to M - 1, and bridge i connects trees U_i and V_i bidirectionally. There is at most one bridge between any pair of trees, and it is possible to get from tree 0 to every other tree by crossing bridges. The distance between two tress is the minimum number of bridges one has to cross to get from one tree to the other (without touching the ground). Alessandro, the zookeeper, wants to add a new bridge to make the monkey area fancier. However, he is facing a problem: the monkey sitting on tree 0 and the one sitting on tree N - 1 are sworn enemies, and if he were to make them fight he would be fired instantly. The monkeys would fight if, after installing the new bridge, the distance between tree 0 and N - 1 was less than before...