Problem G: Yu-kun Likes a Treasure

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらい財宝が大好きだ。ゆう君は今日も財宝を探すため洞窟を探索する予定だ。そこでゆう君は洞窟の地図から、洞窟を全て見て回る際に歩く距離を求めるプログラムを書くことにした。

Problem

洞窟の情報とゆう君の初期位置が与えられる。Fig.1のように、 洞窟は2次元平面上の多角形で表される部屋が、１つ以上繋がった集合で構成される。部屋が別の部屋と接する場合は必ず点で接し、その接点が洞窟の道となり、接点に訪れるとその道を通ったことになる。

道は扉で閉ざされており、扉が閉まっている状態でその道を通ることはできない。扉を開くためには部屋の中にちょうど１つだけ存在するボタンを押す必要がある。ボタンは2次元平面上の点として表される。

ゆう君はボタンが存在する点を訪れることでボタンを押すことができる。ボタンを押すと部屋にある全ての扉が開く。Fig.1では部屋の中にある丸がボタンを表し、顔のマークがゆう君を、そして矢印が指しているボタンがゆう君のいる場所を表す。ボタンを押して扉を開いた後、道を通るとすぐに全ての扉は閉まる。そのため、そこから別の部屋へと移動するためには再度その部屋の中にあるボタンを押す必要がある。ゆう君は最初、いずれかの部屋の中にあるボタンと同じ場所にいる。

Fig. 1

Fig. 2 に移動の例を示す。番号の付いている矢印はゆう君の移動経路を表す。

次の順番で移動することは可能である。

1 -> 2 -> 3 -> 4

次の順番で移動することは不可能である。

1 -> 4

これは、1の経路で移動し部屋同士の接点を訪れるとその瞬間に扉が閉まるからである。

Fig. 2

ゆう君が洞窟内の全ての道を通り、再度初期位置に戻ってくるまでにかかる移動距離の最小値を出力せよ。ただし、同じ道を何度通っても良い。

Input

入力は以下の形式で与えられる。

n m
部屋1の情報
部屋2の情報
…
部屋nの情報

n,mはそれぞれ洞窟を構成する部屋を表す多角形の数、ゆう君が最初にいる部屋の番号を表す。

部屋の情報は次の形式で与えられる。

p
x1 y1
x2 y2
…
xp yp
bx by

pは多角形の頂点数を表す。(x_i,y_i) と (x_i+1,y_i+1) の頂点を繋いだ線分が多角形の一辺である。ただし、p番目の頂点は１番目の頂点と繋がる。 (bx,by) は多角形の内部にあるボタンの位置を表す。多角形は反時計回りで与えられる。

Constraints

入力は以下の制約を満たす。

• 1 ≤ n ≤ 15
• 1 ≤ m ≤ n
• 3 ≤ p ≤ 20
• 0 ≤ x,y,bx,by ≤ 1000
• 多角形は反時計回りで与えられる
• 多角形が別の多角形を内包するようなことはない
• 多角形はその内部 ( 多角形の辺は含まない ) にちょうど１つだけボタンを持つ
• 任意の異なる２つの多角形は共通な面積を持たない
• 任意の異なる２つの多角形a,bにおいて、aとbの接点は高々１つしかない
• 任意の異なる２つの多角形a,bにおいて、直接または１つ以上の多角形を経由することでaからbへ移動することができる

Output

ゆう君が初期位置から全ての道を通って再度初期位置に戻ってくるまでにかかる移動の距離の総和の最小値を出力せよ。小数点以下は何桁数字を出力しても構わない。ただし、解答の誤差は0.00001(10^-5)を超えてはならない。

Sample Input1

3 1
4
0 4
2 4
2 7
0 7
1 6
5
1 0
6 0
4 5
2 2
1 4
4 2
3
2 6
6 4
6 7
5 6

Sample Output1

14.6502815399

Sample Input2

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

Sample Output2

8.0644951022

Sample Input2

4 4
3
0 5
3 8
0 8
1 7
3
1 3
4 3
1 6
2 4
5
2 0
7 0
7 2
3 2
2 3
6 1
3
6 2
7 7
2 7
6 6

Sample Output2

18.9356648257

---