二次元平面上に $N$ 個の格子点 $(x_i, y_i)$ があり、順に $1$ から $N$ への番号がつけられています。どの 3 点も一直線上にはありません。いくつかの点の間には $M$ 本の線分が引かれています。$i$ 本目の線分は点 $u_i$ と $v_i$ とを結んでいます。どの 2 本の線分も端点以外では交差しません。
これを頂点数 $N$、辺数 $M$ の平面グラフと見たとき、連結となっています。また、以下の性質を満たしています。
このとき、線分によって構成される多角形であって、内部に平面グラフの頂点および辺を含まないものの面積の最大値を 2 倍した値 (整数になることが証明できます) を求めるプログラムを作成してください。
なおここでいう多角形とは、平面グラフ上の同じ頂点を二度以上通らないサイクルの辺によって形成される閉曲線のことを指すものとします。
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
答えを 1 行に出力せよ。
3 3
10 10
11 10
10 11
1 2
1 3
2 3
1
三辺の長さが $1, 1, \sqrt{2}$ の二等辺三角形を形成しています。
11 15
-61 100
-60 100
-60 101
-61 101
11 11
11 10
12 10
12 11
10 8
13 8
14 9
1 2
2 3
3 4
1 4
2 5
5 6
5 8
6 7
7 8
6 8
6 9
9 10
10 11
6 11
1 9
395