這天，小明在玩迷宮游戲。

迷宮為一個(gè) n × n 的網(wǎng)格圖，小明可以在格子中移動(dòng)，左上角為 (1, 1)，右下角 (n, n) 為終點(diǎn)。迷宮中除了可以向上下左右四個(gè)方向移動(dòng)一格以外，還有 m 個(gè)雙向傳送門可以使用，傳送門可以連接兩個(gè)任意格子。

假如小明處在格子 (x₁, y₁)，同時(shí)有一個(gè)傳送門連接了格子 (x₁, y₁) 和 (x₂, y₂)，那么小明既可以花費(fèi) 1 的步數(shù)向上下左右四個(gè)方向之一走一格 (不能越過(guò)邊界)，也可以花費(fèi) 1 的步數(shù)通過(guò)傳送門走到格子 (x₂, y₂) 去。

而對(duì)于同一個(gè)迷宮，小明每次進(jìn)入的初始格子是在這 n × n 個(gè)格子中均勻隨機(jī)的 (當(dāng)然運(yùn)氣好可以直接隨機(jī)到終點(diǎn))，他想知道從初始格子走到終點(diǎn)的最短步數(shù)的期望值是多少。

輸入共 1 + m 行，第一行為兩個(gè)正整數(shù) n, m。

后面 m 行，每行四個(gè)正整數(shù) x_i1, y_i1, x_i2, y_i2 表示第 i 個(gè)傳送門連接的兩個(gè)格子坐標(biāo)。

輸出共一行，一個(gè)浮點(diǎn)數(shù)表示答案 (請(qǐng)保留兩位小數(shù))。

2 1
1 1 2 2

0.75

由于傳送門的存在，從 (1, 1) 出發(fā)到終點(diǎn) (2, 2) 只需要一步；而從 (1, 2) 和 (2, 1) 出發(fā)也只需要向下/右走一步；從 (2, 2) 出發(fā)需要 0 步。所以步數(shù)期望為  = 0.75。

對(duì)于 20% 的數(shù)據(jù)，保證 n, m ≤ 20；

對(duì)于 100% 的數(shù)據(jù)，保證 n, m ≤ 2000; x_i1, y_i1, x_i2, y_i2 ≤ n 。