Description

Byteasar is the king of Byteotia, an island in the Ocean of Happiness. The island is convex, and all the towns of Byteotia are located on the shore. One of these towns is Byteburg, the capital of Byteotia.

Every pair of towns is connected by a straight road that follows the line segment between the towns. If two such roads intersect, there is a crossroad at the intersection, and one may freely pass through it.

Some roads are controlled by Bitratio’s guerrilla. Byteasar cannot travel along such roads, but he may cross them at crossroads. He must travel only along roads and may turn only at towns or crossroads.

The towns are numbered from $1$ to $n$ starting from Byteburg and moving clockwise along the shore. Byteasar is currently in town $s$. Find the length of the shortest safe route from town $s$ to Byteburg (town $1$).

Description

Input Format

• The first line contains two integers $n$ and $m$ — the number of towns and the number of roads controlled by the guerrilla.
• The second line contains one integer $s$ — the index of the town where Byteasar is currently located.
• Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$), denoting a road between towns $a_i$ and $b_i$ that is controlled and thus cannot be used for travel (but may be crossed at crossroads).

Output Format

Print a single floating-point number: the length of the shortest safe route from town $s$ to Byteburg (town $1$). The absolute error of your answer must be at most $10^{-4}$.

6 9
-12 -10
-11 6
-4 12
6 14
16 6
18 -2
3 4
1 5
2 6
2 3
4 5
3 5
1 3
3 6
1 6

42.0000000000

Hint

Special judge.

Translated by ChatGPT 5