Consider an undirected connected graph with vertices numbered from $1$ to $N$ and edges numbered from $1$ to $M$.

Little Z performs a random walk on this graph. Initially, Little Z is at vertex $1$. At each step, Little Z chooses one of the edges connected to the current vertex with equal probability and moves to the adjacent vertex along that edge, gaining a score equal to the edge's number. The walk ends when Little Z reaches vertex $N$. The total score is the sum of all scores obtained.

You are asked to assign numbers from $1$ to $M$ to these $M$ edges such that the expected value of the total score obtained by Little Z is minimized.

Input

The first line contains two integers $N$ and $M$, representing the number of vertices and the number of edges in the graph, respectively.

Each of the next $M$ lines contains two integers $u, v$ ($1 \le u, v \le N$), representing an edge between vertex $u$ and vertex $v$.

Output

Output a single real number representing the minimum expected value, rounded to 3 decimal places.

Examples

Input 1

3 3
2 3
1 2
1 3

Output 1

3.333

Note 1

Edge $(1,2)$ is numbered $1$, edge $(1,3)$ is numbered $2$, and edge $(2,3)$ is numbered $3$.

Subtasks

$30\%$ of the data satisfies $N \le 10$.

$100\%$ of the data satisfies $2 \le N \le 500$, and the graph is an undirected simple connected graph.