문제

2020年，世は大グラフ時代．世界は「グラフは辺から先に生まれた」と主張する辺派と，「グラフは頂点から先に生まれた」と主張する頂点派に大きく二分され，混沌を極めていた．主張をぶつけあう両派が行き着いた戦いの究極形が，グラフを用いたとある 2 人ゲームである．今日も辺派のエッジ男さんと頂点派のヴァーテックス子さんが，これからこのゲームで競い合う予定だ．

このゲームではまず N 頂点 M 辺の有向グラフが与えられる．このゲームは 3 つのフェイズからなり，先手フェイズ，後手フェイズ，評価フェイズの順に進行する．

1. 先手フェイズ: 先手は辺派のエッジ男さんであり，このフェイズでは M 本の辺からちょうど 1 本の辺をランダムに選ぶための確率をエッジ男さんが設定する．すなわち，すべての辺に対し i 番目の辺が選ばれる確率 e_i を好きに割り振る．ここで，各 e_i は 0 以上 1 以下の実数であり，すべての e_i の和はちょうど 1 でなければならない．
2. 後手フェイズ: 後手である頂点派のヴァーテックス子さんは，N 個の頂点からちょうど 1 つの頂点をランダムに選ぶための確率を設定する．すなわち，すべての頂点に対し j 番目の頂点が選ばれる確率 v_j を好きに割り振る．辺と同様，各 v_j は 0 以上 1 以下の実数であり，すべての v_j の和はちょうど 1 でなければならない．ここで後手は，先手が辺に割り当てた確率を自由に見てから確率を割り振ることができる．
3. 評価フェイズ: 割り当てられた確率に基づき，辺を 1 本と頂点を 1 つ，独立にランダムに決定する．選ばれた辺と頂点の関係によって，ゲームのスコアを以下のように決める．

• 頂点が有向辺の始点であれば，スコアは -1 である．
• 頂点が有向辺の終点であれば，スコアは 1 である．
• 頂点が有向辺の始点でも終点でもなければ，スコアは 0 である．

このゲームにおいて後手の頂点派のヴァーテックス子さんはスコアの期待値を最小化するように確率を割り振る．これはもちろん，頂点が辺よりも先に来るべきだと考えているからだ．一方先手の辺派のエッジ男さんは，後手のヴァーテックス子さんがスコアの期待値を最小化する戦略を取ることを踏まえた上で，スコアの期待値を最大化するように確率を割り振る．これは言わずもがな，辺が頂点よりも先に来るべきだと考えているからだ．与えられたグラフにおいて 2 人が上記の戦略に基づいて辺・頂点に確率を割り当てるとき，スコアの期待値を求めよ．

입력

入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．

NMa1b1…aMbM

1 行目はゲームで用いる有向グラフの頂点数 N (2 ≤ N ≤ 10⁴) と辺数 M (1 ≤ M ≤ 10⁴) からなる． 続く M 行はグラフの有向辺の情報を表す．M 行のうちの i 行目は，i 番目の辺の始点が a_i (1 ≤ a_i ≤ N) 番目の頂点であり，終点が b_i (1 ≤ b_i ≤ N) 番目の頂点であることを表す． 与えられるグラフには自己ループがない．すなわち，すべての1 ≤ i ≤ M について，a_i ≠ b_i を満たす． 与えられるグラフには多重辺がない．すなわち，すべての 1 ≤ i < j ≤ M について，a_i ≠ a_j または b_i ≠ b_j のいずれかを満たす．

入力の終わりは 2 つのゼロからなる行で表される．

출력

与えられたグラフにおいて，両者が上記の各々の最適な戦略を取ったときの，ゲームのスコアの期待値を 1 行に出力せよ．結果は 10⁻¹⁰ 以上の誤差を含んではいけない．

제한

힌트