2279 - [Ncpc2010]Around the track

给你一个图。你找一条欧拉回路出来，使得沿这条路转过的角度最小。 图很特殊，一个结点出来，要么恰好有2条边，或者恰好有4边 一个欧拉回路，即它必须遍历每个图形的边恰好一次，并回到起 点。 （输入的跑道保证其欧拉回路的存在）.总的转弯弧度就是在这个回路中， 在每个结点处需要的转弯弧度的总和，在一条直线上继续行进不用转弯。每一段 跑道都是可以双向行驶的。

Input

Oneline with 3 < = N < = 10000{the number of nodes{and N < = M < = 2N {the number of edges. N lines with the x and y coordinates o feachnode,inorder.0 < = x;y < = 10000.The nodes have unique coordinate pairs. M lines with two space separated numbers i and j,denoting an edge between nodes i and j.The nodes are 0-indexed. 第一行 两个数,N , M . (3<=N <=10000, 代表结点的个数。N<=M<=2N 边的个数) 接下来N行，依次组出每个结点的坐标 0<=x,y<=10000 。每个结点的坐标是唯一 的 接下来M行,每两个数，表示i, j之间存在一条边.(结点从0开始编号)

Output

欧拉回路上最小的所需转弯的弧度和

Examples

Input

12 19
1077 2677
7473 4262
1095 8844
84 7875
7241 7320
9143 4888
4524 1947
4652 1260
3503 7882
4692 223
9745 5245
2037 2387
0 1
0 2
1 4
1 2
1 3
3 4
4 6
4 5
5 8
5 6
5 7
6 8
6 7
7 9
7 8
8 9
9 11
9 10
10 11

Output

37.699111843077446
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题