Bridge Park

Time limit1sMemory limit512 MB

Summary

Given a connected planar straight-line graph on convex-position vertices, add the fewest non-crossing edges so the graph becomes 2-edge-connected.

Level: Hard8 of 10
Topics: Graph, Greedy, Dynamic programming
Solved: No attempts yet

Problem

A park has $n$ small islands and $m$ bridges. The islands stand at the vertices of a convex polygon, a simple polygon whose interior angles are all smaller than 180 degrees. An island is a point and a bridge is a straight line segment. Every bridge joins exactly two islands, and two different bridges meet only at an island they share.

The bridges connect all islands, so a visitor standing on one island can walk to every other island.

A park with 7 islands and 7 bridges

One day a bridge broke and tourists were stranded on islands they could not leave. The park committee wants to build extra bridges so that all islands stay connected even after any single bridge breaks. An extra bridge is also a straight line segment between two islands, and it must not meet another bridge except at a shared island. Two islands that a bridge already joins cannot be joined again, because the new segment would lie on top of the old one.

Write $(i, j)$ for the bridge joining islands $i$ and $j$ . The park in the figure has the bridges $(0, 1)$ , $(0, 3)$ , $(1, 2)$ , $(1, 3)$ , $(3, 6)$ , $(4, 5)$ and $(5, 6)$ . If $(3, 6)$ breaks, the islands fall into the two groups $\{0, 1, 2, 3\}$ and $\{4, 5, 6\}$ . If $(5, 6)$ breaks, they fall into $\{0, 1, 2, 3, 6\}$ and $\{4, 5\}$ . If $(0, 3)$ breaks, all islands stay connected. Building the two bridges $(2, 3)$ and $(3, 4)$ makes the park survive the loss of any single bridge.

Given the islands and the bridges of the park, find the smallest number of extra bridges that keeps all islands connected after any single bridge breaks.

Input

The first line has two integers $n$ and $m$ ( $3 \le n \le 100000$ , $n - 1 \le m \le 2n - 3$ ), the number of islands and the number of bridges. The islands are numbered $0$ through $n - 1$ , and the list $(0, 1, 2, \ldots, n - 1)$ is the order in which they appear along the boundary of the convex polygon counterclockwise.

Each of the next $m$ lines has two integers $i$ and $j$ ( $0 \le i, j \le n - 1$ ) describing the bridge $(i, j)$ . The given bridges connect all islands, and two different bridges meet only at an island they share.

Output

Print one integer on a single line: the smallest number of extra bridges such that all islands stay connected after any single bridge breaks.

Examples2

Example 1
Input
```
7 7
0 1
0 3
1 2
1 3
3 6
5 6
4 5
```
Expected output
```
2
```
Example 2
Input
```
6 8
0 1
4 5
1 5
2 1
4 3
1 3
2 3
0 5
```
Expected output
```
0
```