时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一个 \(n\) 个点 \(m\) 条边的无向连通图，顶点从 1 编号到 \(n\)，边从 \(1\) 编号到 \(m\)。
小 Z 在该图上进行随机游走，初始时小 Z 在 1 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 \(n\) 号顶点时游走结束，总分为所有获得的分数之和。
　　现在，请你对这 \(m\) 条边进行编号，使得小 Z 获得的总分的期望值最小。

【输入格式】

　　第一行是两个整数，分别表示该图的顶点数 \(n\) 和边数 \(m\)。
　　接下来 \(m\) 行每行两个整数 \(u,v\)，表示顶点 \(u\) 与顶点 \(v\) 之间存在一条边。

【输出格式】

　　输出一行一个实数表示答案，保留三位小数。

【输入输出样例】

　Input

3 3
2 3
1 2
1 3

　Output

3.333

【样例解释】

　　边 (1,2) 编号为 1，边 (1,3) 编号 2，边 (2,3) 编号为 3。

【数据限制】

　　对于 \(30\%\) 的数据，\(1≤n≤10\)
　　对于 \(100\%\) 的数据，\(2≤n≤500\)，\(1≤m≤125000\)，\(1≤u,v≤n\)，给出的图无重边和自环，从 1 出发可以到达所有的节点。

【来源】

　　Mr.he