acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem A

nmマス計算

あなたは小学校の情報の先生である.職員室で担任の先生と話をしていると,今年の夏休みの宿題として 100 マス計算を拡張した nm マス計算が出されたと聞いた.

宿題は児童が他の児童の回答を写して提出するのを防ぐため,また各児童の習熟度に合わせて課題の難易度調整を行うために,各児童には異なる計算課題が出題された.具体的には以下の通りである.

  • 計算結果の記入部が nm 列ある方眼用紙が配られる.
  • 更に長さ n の整数列 a, 長さ m の整数列 b も配られる.これは nm マス計算の縦部と横部に対応する.
  • 計算結果のマスは左上が (1,1) ,左下が (n,1),右下が (n,m) となっている.
  • 児童はマス (i, j) に対して ai × bj の結果を 10 進法表記で書き込む.このとき,先頭に不必要な 0 をつけることはない.

例えば縦部 a = {10, 2, 5}, 横部 b = {1, 1, 6} として出題された児童は,図 A-1 の様にマスに記入することになる.

図 A-1 nm マス計算の例

さて夏休みの宿題を出したは良いものの,評価のためには児童が正しく課題をこなしたか確認する必要がある.しかし先生の仕事は忙しいので,沢山いる児童の nm マス計算の結果を検算するのは大変である.そこで児童には,計算結果の記入部に記入した数字 0-9 の個数を別に提出してもらうことにして,この個数が合っているかで評価することにした. 図 A-1 を例にすると,0 は 4 個,1 は 3 個,2 は 3 個,3 は 1 個,5 は 2 個,6 は 1 個,他は 0 個である.

しかしこの個数を求めるのも一苦労である.万が一この想定解を間違えて児童に誤った評価を下そうものなら児童の人生を左右してしまうし,先生も PTA からのお叱りを受けてしまう. そこで担任の先生は,優秀な情報の先生であるあなたに,正解解答を作成してもらうことにした.あなたは解答を求めるプログラムを書くことにした.

Input

入力は次の形式の最大 100 個のデータセットからなる.各データセットは次の形式で表される.

n m a1 a2 ... an b1 b2 ... bm

データセットの最初の行は,二つの整数 nm からなる.n は縦の行数,m は横の列数である.この値は 1 ≤ n, m ≤ 100 を満たす. 2 行目は整数列 a の値が n 個ある.ai (1 ≤ i ≤ n) は i 行目の値を表す. 3 行目は整数列 b の値が m 個ある.bj (1 ≤ j ≤ m) は j 列目の値を表す. これらの値は 1 ≤ ai, bj ≤ 1,000 を満たす.

入力の終わりはゼロふたつからなる行で表される.

Output

各データセットについて,与えられた nm マス計算に書き込まれる数字 0–9 の個数 c0 c1 ... c9 を 1 行に空白区切りで出力せよ.

Sample Input

2 4
2 1
1 4 2 3
3 3
10 2 5
1 1 6
10 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
8 6
3 1 4 1 5 9 2 6
2 7 1 8 2 8
8 15
3 10 5 16 8 4 2 1
11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
0 0

Output for the Sample Input

0 1 2 1 2 0 1 0 1 0
4 3 3 1 0 2 1 0 0 0
28 24 27 15 23 15 17 8 15 6
4 12 16 5 11 2 6 4 11 1
59 42 41 20 28 18 29 7 23 1
(End of Problem A) A B C D E F G H

Problem B

爆発の連鎖

あなたは爆弾を使ったゲームで遊んでいる.このゲームのフィールドは幅 W マス,高さ H マスのマス目状である.このフィールドの左から x 列目,上から y 行目のマスは (x, y) と表される.

このフィールド上に N 個の爆弾が配置されており,i 番目の爆弾の位置は (xi, yi) である.このゲームの爆弾は,爆発したとき爆弾のあるマスから上下左右それぞれの方向 D マス以内の十字型の領域内にある爆弾を誘爆して消失する.また,爆弾は別の爆弾によって誘爆されたときにも連鎖して爆発する.この爆発は他に爆発する爆弾が無くなるまで続く.

このゲームの攻略には,ある爆弾を爆発させたときに合計で何個の爆弾が爆発するか知ることが重要である.あなたは攻略を有利に進めるためのプログラムを作ることにした.

例として,入力サンプルの最後のデータセットは以下の図のようになる.このデータセットでは (4, 1) の位置にある 4 番目の爆弾が最初に爆発する.その後,以下のように爆発が連鎖する.

  • (4, 1) の位置の爆弾から上下左右それぞれの方向 3 マス以内にある爆弾を誘爆する.
  • (5, 1)(4, 4) の位置の爆弾が誘爆により連鎖して爆発し,各々の上下左右それぞれの方向 3 マス以内にある爆弾を誘爆する.
  • (3, 4)(1, 4) の位置の爆弾が誘爆により連鎖して爆発する.このとき新しく誘爆される爆弾はない.

よって (4, 1) の位置にある爆弾が爆発すると合計で 5 つの爆弾が爆発する.

Input

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

W H N D B x1 y1 x2 y2 ... xN yN

各データセットは N+1 行からなる.

1 行目はフィールドの幅 W (1 ≤ W ≤ 100),高さ H (1 ≤ H ≤ 100),爆弾の数 N (1 ≤ N ≤ min(100, WH)),爆弾の爆発の大きさ D (1 ≤ D ≤ 100),最初に爆発する爆弾の番号 B (1 ≤ B ≤ N) を表す整数である.

2 行目から続く N 行はそれぞれ N 個の爆弾の位置を表す.i + 1 行目は i 番目の爆弾の位置 (xi, yi) を表す整数であり 1 ≤ xi ≤ W1 ≤ yi ≤ H を満たす.各データセットについて同じマスに複数の爆弾が配置されることはない.

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

Output

各データセットについて,最初に B 番目の爆弾が爆発したときに,最終的に爆発する爆弾の数を 1 行で出力せよ.

Sample Input

10 5 5 3 1
1 5
2 5
5 5
5 4
10 5
50 50 1 100 1
25 25
1 100 7 10 4
1 5
1 10
1 40
1 50
1 55
1 63
1 74
3 3 5 3 5
1 1
1 3
3 1
3 3
2 2
20 20 10 10 1
5 5
20 5
5 10
20 8
5 20
10 10
17 17
11 10
8 9
11 20
5 5 7 3 4
1 4
2 2
3 4
4 1
4 4
5 1
5 5
0 0 0 0 0

Output for the Sample Input

4
1
4
1
6
5
(End of Problem B) A B C D E F G H

Problem C

忍ぶべし

あなたにはあるミッションが課せられている.それは,無限に広がる二次元グリッド上にある降下地点マス (sx, sy) へと人員を送り込み,その後敵陣に悟られることがないよう移動をサポートし,敵の基地があるマス (gx, gy) への潜入を成功させることだ.あなたはこの重要なミッションの潜入役を,忍び込みのプロ・忍小宮に託した.

忍小宮は上下左右の隣接した 4 マスのいずれかに移動することを繰り返し,敵の基地を目指す.また,迅速に任務を遂行するため,降下地点から敵の基地まで必ず最短距離となるよう移動を行う.

事前の偵察によるとこの 2 次元グリッド上には敵のセンサーが N 個あり,i 番目のセンサーは (xi, yi) を中心として 1 辺 2ri + 1 の正方形領域,すなわち |x - xi| ≤ ri かつ |y - yi| ≤ ri を満たすような全てのマス (x, y) をカバーしていることがわかっている.忍小宮は 1 つ以上のセンサーにカバーされている領域に入ると敵に発見されてしまう.

ここで問題になるのは,現在のセンサーの配置ではどうしても忍小宮が最短距離の移動で敵の基地まで辿り着けない可能性があることだ.この場合,あなたはサポート役としてセンサーを破壊しなければならない.リスク・コストを軽減するため,破壊するセンサーの個数はできる限り少なくしたい.

例として,入力サンプルの 4 番目のデータセットは図 C-1 のようになる.図 C-2 のように 3 つのセンサーを取り除くことにより,忍小宮は最短距離で敵の基地まで辿り着くことができるようになり,この例ではこれが最小個数である.

図 C-1 入力サンプル 4 番目のデータセットの配置

図 C-2 入力サンプル 4 番目のデータセットにおける最小個数の例

勘のいいあなたはお気付きだろう.どうしてもセンサーに検知されてしまう忍小宮より,センサーに検知されずに破壊できるあなたの方が,忍び込みスキルが高いということに.そう,何を隠そう忍小宮は自分を忍び込みのプロだと勘違いしているだけのただの一般人であり,あなたこそが忍び込ませのプロ・忍駒瀬だったのだ.何も知らない忍小宮には気付かれず密やかに必要最低限のセンサーを破壊し,あたかも自分は忍び込みのプロなのだと忍小宮に思い込ませることが,忍び込ませのプロとしてのあなたの矜恃だ.まずはプロとしてあらかじめコストを見積もるため,忍小宮の任務を成功させるには最小でいくつのセンサーを破壊する必要があるか求めて欲しい.

Input

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

N sx sy gx gy x1 y1 r1 ... xN yN rN

最初の行はセンサーの個数 N (1 ≤ N ≤ 105) を表す整数からなる. 2 行目の sx, sy は忍小宮の降下地点 (sx, sy) を,gx, gy は敵の基地の位置 (gx, gy) をそれぞれ表し,1 ≤ sx, gx ≤ 10001 ≤ sy, gy ≤ 1000 を満たす. 続く N 行の i 行目は i 番目のセンサーの情報であり,センサーが位置 (xi, yi) を中心に 1 辺 2ri +1 の正方形領域をカバーしていることを表す.1 ≤ xi ≤ 10001 ≤ yi ≤ 10000 ≤ ri ≤ 1000 をそれぞれ満たす. ここで,(sx, sy)(gx, gy) は必ず異なるマスである.

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

Output

各データセットについて,忍小宮が (sx, sy) から (gx, gy) までセンサー領域を通らず最短距離で移動できるようにするために破壊する必要があるセンサーの最小個数を 1 行に出力せよ.

Sample Input

3
2 2 4 5
1 1 1
1 5 2
4 3 1
5
1 2 1 1
5 3 2
8 8 6
6 9 2
1 7 3
4 4 1
1
3 7 1 1
2 5 10
9
25 30 90 100
50 50 15
60 30 20
70 35 15
90 50 10
80 70 20
65 85 15
40 70 35
25 55 20
25 80 20
0

Output for the Sample Input

2
0
1
3
(End of Problem C) A B C D E F G H

Problem D

そこそこバランスのとれた括弧列

「そこそこバランスのとれた括弧列」とは,以下のいずれかの条件を満たす文字列である.

  • 空文字列
  • そこそこバランスのとれた括弧列 A が存在し,'(' を 1 個または 2 個, A, ')' を 1 個または 2 個 をこの順に結合した文字列
  • 空文字列でないそこそこバランスのとれた括弧列 A, B が存在し,A, B をこの順に結合した文字列

たとえば,'())' や '())(()()' などはそこそこバランスのとれた括弧列であるが,'((' や '()))((()' などはそこそこバランスのとれた括弧列ではない.

'(' と ')' のみからなる文字列 S が与えられる.S がそこそこバランスのとれた括弧列になるように括弧を追加する.ただし,括弧はどの位置に追加しても良い.追加する最小の括弧の数を求めよ.

Input

入力は最大 50 データセットからなる.各データセットは 1 行からなり,長さが 1 以上 2 × 105 以下の '(' と ')' のみからなる文字列が与えられる.

入力の終わりは,'#' からなる行で表される.文字列の長さの合計は 5 × 106 を超えない.

Output

各データセットについて,そこそこバランスのとれた括弧列にするために追加する最小の括弧の数を 1 行に出力せよ.

Sample Input

(()
())()(()
((()))))
))(()(
))()()))()(((())))))))((((()(
#

Output for the Sample Input

0
0
0
2
5
(End of Problem D) A B C D E F G H

Problem E

Edamame Energy Engineering

バイオベンチャーの ICPC (International Cucumber Planting Company) は燃料用枝豆の育成に取り組んでいる.彼らがベンチャーキャピタルに提出した事業計画によると,ICPC 社の技術で特別に品種改良した枝豆を特定の薬品で化学処理することで燃料用エタノールを得ることが可能らしい(もともとはきゅうりの改良に取り組んでいたが,こちらはうまくいかなかった).

その枝豆がまもなく収穫の時期を迎えようとしている.この枝豆の鞘には M 粒の豆が一列に並んでおり,粒ごとに異なる特性を持っているので本来はそれぞれ異なる化学処理が必要となる.

化学処理に用いられる薬品は全部で N 種類ある.それぞれの豆粒には 2 個の特性があり,そのどちらかが満たされていれば燃料にすることが可能である.特性には「ある薬品を用いる」ものと「ある薬品を用いない」ものの 2 種類がある.

  • 特性 P(x): 種類 x の薬品が有効である(種類 x の薬品を用いると処理できる)
  • 特性 Q(x): 種類 x の薬品によって阻害される,その豆粒に有効な自己分解酵素を持っている(種類 x の薬品を用いなければ処理できる)

たとえば,ある豆粒が P(x)Q(y) の特性を持っているとすると,この豆粒は種類 x の薬品を用いることで処理できるほか,種類 x の薬品が用いられていない場合でも種類 y の薬品さえ用いられていなければ,処理することができる.また,ある豆粒が持つ 2 個の特性は同じタイプである場合もあり,たとえば,P(x)P(y) の特性を持っているとすると,この豆粒は種類 x または y の薬品を用いると処理することができる.

長きにわたる研究開発で資金が底をつきかけている ICPC 社には,枝豆を 1 粒ずつ取り出してそれぞれに適切な処理を行うような設備に投資する余力は残されていなかった.代替案として,0 種類以上の薬品を混合して作った処理液を用いて,枝豆の両端から 0 個以上の連続する豆粒を捨て,中央の残った豆粒をすべてまとめて処理する工程を採用することにした.このとき,薬品や枝豆は特性に表現されている以外の相互作用を起こさないことがわかっている.しかし,処理できていない豆粒が残っていると後工程に支障が出るのでこれは許されない.

もちろん,設備の収率を上げるには捨てる豆粒ができるだけ少ないほうがよい.ICPC 社のソフトウェアエンジニアであるあなたの仕事は,処理液に用いる薬品の種類を適切に選ぶことでできるだけ多くの豆粒を使えるように計画するプログラムを書くことである.

たとえば,入出力例の 1 つ目のデータセットでは,種類 1 と 2 の薬品を混合した処理液を用いることで,1 番目から 3 番目までの豆粒を処理できる.しかし,種類 1 と 2 の薬品をそれぞれ使う・使わない全 4 通りの処理液のいずれでもどれか 1 つの豆粒は処理できない.したがってこのデータセットの答えは 3 である.2 つ目のデータセットにあるように,1 つの豆粒が同じ特性を重複して持つ場合もあるので注意せよ.この場合も 2 つのうちのいずれかの条件を満たしていれば処理できる.3 つ目のデータセットでは,いずれの薬品も用いない処理液を用いることですべての豆粒を処理できる.

Input

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

N M a1 b1 ... aM bM

最初の行は薬品の種類数 N (1 ≤ N ≤ 2000) と枝豆に含まれる粒数 M (1 ≤ M ≤ 2000) がこの順で与えられる.続く M 行に豆粒に関する情報が 1 行ずつ与えられる. 1 + i 行目には端から数えて i 番目の豆粒の特性を表す 2 つの整数 aibi が与えられる.この整数を x とすると -N ≤ x ≤ N, x ≠ 0 を満たし,x が正のときは i 番目の豆粒は種類 x の薬品で処理できること,すなわち特性 P(x) を持っていること,x が負のときは i 番目の豆粒は種類 |x| の薬品を用いなければ処理できること,すなわち特性 Q(|x|) を持っていることをそれぞれ意味する.

入力の終わりは 2 つの 0 からなる行で表される.

Output

各データセットに対し,処理に使用することができる最大の豆粒の数を 1 行に出力せよ.

Sample Input

2 4
1 2
1 -2
-1 2
-1 -2
1 2
1 1
-1 -1
10 5
-1 -2
-3 -4
-5 -6
-7 -8
-9 -10
3 3
1 -1
2 -2
3 -3
2 5
1 1
2 2
-1 -1
2 2
1 1
0 0

Output for the Sample Input

3
1
5
3
3
(End of Problem E) A B C D E F G H

Problem F

アローダイス

アローダイス (arrow dice) とは,立方体の各面の中央部にその面を構成する 4 辺のいずれかの中心を向いた矢印が 1 つずつ書かれたものである.図 F-1 にその一例を示す.

図 F-1 アローダイスの一例

ここで,2 つのアローダイスの相違度を「それぞれを任意に回転させたあとで立方体として完全に重なり合うように重ね合わせたときに,対応する面について向きの異なる矢印の個数の最小値」と定義する.

n 個のアローダイスが与えられるので,すべてのペアに対してその相違度を求めてほしい.

Input

入力は最大 50 データセットからなり,各データセットは次の形式で表される.

n x1,1x1,2...x1,5 x2,1x2,2...x2,5 ... x5n,1x5n,2...x5n,5

各データセットの 1 行目には与えられるアローダイスの個数 n (2 ≤ n ≤ 200),続く 5n 行には n 個のアローダイスの情報が 5 行ずつ与えられる.5i-4 行目から 5i 行目までの入力が i 個目のアローダイスの情報である.

各アローダイスは 5 × 5 のグリッドで表現される. グリッド上で '^', 'v', '<', '>' はそれぞれ上下左右を向いた矢印が書かれたマスを表し,'.' は余白を表す. グリッドから余白を取り除いて得られる図形に対して,隣接するマスの間を山折りにして得られる立体がこのグリッドが表現するアローダイスである.入力として与えられるどの図形に関しても,正しく組み立てることでアローダイスが 1 つ出来上がることが保証されている. 例えば,サンプルの最初のケースの 1 つ目の入力が表す図形は図 F-2 の通りであり,図 F-1はこれを組み立てて得られるアローダイスを表している.

図 F-2

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

Output

各データセットに対して,i 行目の j 文字目に i 個目のアローダイスと j 個目のアローダイスの相違度を出力せよ.つまり,長さ n の数字列を n 行出力することになる.なお,2 つのアローダイスの相違度は 1 桁の整数となることが証明できる.

Sample Input

3
..^..
.<v>.
..>..
..<..
.....
..^..
.<^>.
..>..
..<..
.....
..>..
..^v.
.^>..
.v...
.....
8
..<^.
...^<
...<.
...<.
.....
.<...
<>...
.^<..
.v...
.....
.....
.....
.>...
^>><.
<....
.....
...<.
..v^.
..>..
.<v..
.....
...<.
..^v.
...<>
...>.
.....
...^.
..>v.
.v^..
.<...
.....
..<..
.vv..
^v...
.^...
.....
....>
.v^vv
...<.
.....
0

Output for the Sample Input

010
101
010
02222232
20432043
24013422
23103331
22330223
20432043
34232402
23213320
(End of Problem F) A B C D E F G H

Problem G

競プロは小惑星探査の役に立つ

JAG (Japan Aerospace-exploration Group) の小惑星探査機群まわりこみやが 2019 年に地球を飛び立ってから 10 年,いよいよ目標の小惑星帯 ICPC-2020 へ接近する日が近づいてきた.この探査プロジェクトにおいては,複数の探査機がそれぞれ異なる小惑星からサンプルを採取することになっている.ところが,この 3 日前になって JAG の宇宙観測部門がある重大な見落としに気がついた.彼らの報告によると,まわりこみやの現在地から ICPC-2020 の間にはいくつもの障害物が存在し,このままの軌道ではまわりこみやは衝突してしまうかもしれないらしい.

すぐさま緊急会議が行われ,エンジン噴射で機体を制御して障害物を回避することになった.必要な制御プログラムの実装は JAG の技術者であり競技プログラマーでもあるあなたが担当することも決まった.あなたがこれから書くプログラムの仕様は競技プログラミング風に言えば次のようになるだろう.

Q 機のまわりこみやの機体とそれぞれが目標とする小惑星の位置が xy-平面上の点として与えられる(宇宙工学的要請によりまわりこみやはこの平面上しか動けない.まわりこみやと小惑星は障害物と比べて十分小さく,大きさは無視できる).また,この平面と交差する障害物の情報も複数の多角形として与えられる.まわりこみやはこの平面上でいくつかの線分からなる折れ線状の経路に沿って移動することができ,これによって障害物にぶつかることなく ICPC-2020 の座標に到達することが目標である(まわりこみやが多角形の辺上に存在することはできる). この宙域には弱い重力が作用しており,線分に沿って移動する際に y 座標が増加しないなら噴射をする必要はないが,y 座標が増加するときは y 座標 1 あたり 1 ジュールの割合でエネルギーを使って噴射する必要がある.探査機のエネルギーを使いすぎると帰還が困難になってしまうので,消費エネルギーはできるだけ少なくしたい. それぞれの機体について,目標の小惑星に到達するのに必要な最小のエネルギーを求めよ.

Input

入力は最大 50 データセットからなり,各データセットは次の形式で表される.

N Q v1 x1,1 y1,1 ... x1,v1 y1,v1 v2 x2,1 y2,1 ... x2,v2 y2,v2 ... vN xN,1 yN,1 ... xN,vN yN,vN sx1 sy1 gx1 gy1 ... sxQ syQ gxQ gyQ

最初の行には障害物を表す多角形の個数 N (1 ≤ N ≤ 10) と探査機の個数 Q (1 ≤ Q ≤ 1000) がこの順で与えられている.この次に N 回にわたって多角形の情報が与えられる.それぞれの多角形は次の形式で表される.

i 個目の多角形の頂点数 vi (3 ≤ vi ≤ 100) が 1 行目に与えられる.続く vi 行に,1 行に 1 頂点ずつ多角形を構成する頂点の座標が与えられる.これらの行には x 座標と y 座標がこの順で与えられている.i 個目の多角形は,ここに登場する頂点を登場する順に辺で結び,最後の頂点と最初の頂点を辺で結ぶと得られる.この多角形は自己交差を持たない単純な多角形であることが保証されている.

多角形の情報に続いて Q 行に渡って探査機と小惑星の情報が与えられる.各行には探査機の座標 (sxi, syi) と目標とする小惑星の座標 (gxi, gyi) がこの順で与えられる.

各データセットにおいて与えられる座標は全て整数であり,x 座標と y 座標の絶対値はともに 1000 を超えない.また,どの 2 つの多角形の面(内部と境界を合わせた点の集合)同士の共通部分も空であること,始点と終点はすべての多角形の外部の共通部分に存在することが保証されている.

入力の末尾は空白で区切られた 2 つの 0 で表される.

Output

各データセットに対し Q 行を出力せよ.Q 行のうちの i 行目には i 番目の探査機に必要な最小のエネルギーを出力せよ.結果は 10−6 以上の誤差を含んではいけない.

Sample Input

1 1
4
1 2
3 2
3 -1
1 -1
0 0 5 0
2 1
4
0 -1
-1 -4
0 -2
1 -4
4
0 1
-1 4
0 2
1 4
0 -3 0 3
4 3
6
0 2
3 2
2 0
3 -2
0 -2
1 0
6
3 0
4 -2
5 -2
4 0
5 2
4 2
7
6 2
7 2
9 1
7 0
7 -2
6 -2
5 0
6
9 0
10 -2
11 -2
10 0
11 2
10 2
0 -1 11 1
11 1 0 -1
11 1 11 -1
0 0

Output for the Sample Input

1.000000000000
8.000000000000
3.000000000000
1.000000000000
0
(End of Problem G) A B C D E F G H

Problem H

辺が先か,頂点が先か

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

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

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

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

Input

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

N M a1 b1aM bM

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

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

Output

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

Sample Input

4 4
1 2
1 3
2 4
3 4
3 3
1 2
1 3
2 3
4 4
1 2
2 3
3 4
4 1
4 3
1 2
1 4
2 3
5 2
1 2
5 4
0 0

Output for the Sample Input

-0.25
-0.333333333333333
0
-0.333333333333333
-0.5
(End of Problem H) A B C D E F G H