Around the Track

After The Stig's identity was revealed, the car show Top Gear urgently needs a new, calm, and anonymous racing driver to replace him, and you have been asked to take the job. However, you are not very fond of driving fast, and especially not around the twisting and turning tracks used on the show. To ease this, one of your algorithmically minded friends suggests that you compute the roundtrip that requires the least total amount of turning.

The track consists of unique, straight roads (edges), and exactly $2$ or $4$ roads always head out of each junction (node). A roundtrip must be an Eulerian circuit: it must traverse every road exactly once and end where it started (such a circuit is guaranteed to exist in the input graph). The total amount of turning is the sum of the turning done at each node, where continuing straight through a node counts as a turn of $0$. Roads can be driven in either direction.

When you enter a node along one road and leave along another, the turning is the absolute change of heading (in radians). If the angle between the two roads is $\theta \in [0, \pi]$, the turn equals $\pi - \theta$: going straight ($\theta = \pi$) is $0$, and a full U-turn ($\theta = 0$) is $\pi$. A degree-$4$ node is visited twice, so you may choose how to pair its four roads into two pairs, as long as the whole route forms a single Eulerian circuit.

One line with the number of nodes $3 \leq N \leq 10000$ and the number of edges $N \leq M \leq 2N$, separated by a space.

$N$ lines with the $x$ and $y$ coordinates of each node, in order ($0 \leq x, y \leq 10000$). All nodes have distinct coordinate pairs.

$M$ lines with two integers $i$ and $j$ separated by a space, denoting an edge between nodes $i$ and $j$. Nodes are $0$-indexed.

Output the least total amount of turning needed to complete an Eulerian circuit, in radians, rounded to exactly six decimal places.

Figure: an illustration of the track from the second example.