Shortest Safe Route

The island of Byteotia is a convex polygon with n towns located on its shore. The towns are numbered in clockwise order from 1 to n. Every pair of towns is connected by a straight road (a chord of the polygon). Some of these roads are controlled by guerrilla forces and are unsafe – Byteasar cannot travel along them. However, he is allowed to cross these unsafe roads at crossroads (i.e. intersection points). Byteasar must travel from town 1 to town n exclusively along safe roads, and he is only allowed to change direction at a town or at a crossroads (i.e. at points where two safe roads intersect).

You are given which roads are safe. Formally, you are given an integer n and an integer m followed by m pairs of integers. Each pair u v indicates that the road connecting town u and town v is safe. The coordinates of the towns are not given explicitly; you can assume that the towns are placed on a unit circle in clockwise order, so that the coordinates of town i are \[ (x_i,y_i)=(\cos\theta_i,\sin\theta_i), \quad \theta_i=\frac{2\pi(i-1)}{n}, \] which guarantees that the towns form a convex polygon.

The safe route may use parts of safe roads. Notice that if two safe roads intersect in a point other than the towns, this intersection is a valid crossroads where Byteasar may switch roads. On each safe road, you can only turn at a town or at an intersection with another safe road. Your task is to compute the length of the shortest safe route from town 1 to town n.

If no safe route exists, output an appropriate message (for this problem, you may assume that a safe route always exists).

The distance between two points \((x_1,y_1)\) and \((x_2,y_2)\) is given by \[ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}. \]

inputFormat

The first line contains two integers n and m (3 ≤ n ≤ 200, 1 ≤ m ≤ n(n-1)/2), where n is the number of towns and m is the number of safe roads.

The following m lines each contain two integers u and v (1 ≤ u, v ≤ n, u ≠ v) representing a safe road between town u and town v. Each safe road is listed at most once.

outputFormat

Print a single real number, the length of the shortest safe route from town 1 to town n. The answer will be accepted if its absolute or relative error does not exceed 10^-6.

sample

4 4
1 2
2 3
3 4
4 1

1.414214