Description

A mini metro network called the 'Nyang-Nyang Line' opened in Cat Village. Stations are connected by direct corridors, and you can move between two connected stations in one hop. All corridors have the same length (no weights). What is the minimum number of corridor hops to go from the start station to the destination? Taking one corridor counts as one move.

Input

Output

Constraints

• •1 ≤ N ≤ 1000
• •Corridors are bidirectional and all have equal weight
• •Duplicate corridors between the same two stations may appear

Examples

7 7
0 1
0 2
1 3
3 4
2 5
5 4
2 6
0 4

3