Downtown One-Way Streets

The councillors of the city of Los Hippopotalamos are overwhelmed with complaints about downtown traffic jams. Most residents refuse to walk and instead ride the local means of transport — the hippos. The downtown lanes are narrow and the hippos are large, so when two hippos meet head-on in a lane they get stuck and block traffic for a very long time. To eliminate these collisions, the councillors have decided to turn every lane into a one-way street.

You are given a map of the town as an undirected planar graph: intersections are the vertices, and each two-way lane between two intersections is an edge. You must assign a direction to every lane, turning each edge into a one-way street. For an intersection, its number of outgoing streets is how many lanes leave it. The councillors want to spread the outgoing traffic as evenly as possible, so they want the largest number of outgoing streets at any single intersection to be as small as possible.

Over all ways of orienting every lane, find the smallest possible value of that maximum, i.e. the minimum achievable value of $\max_v \operatorname{outdeg}(v)$.

The first line contains two integers $N$ and $M$ ($1 \le N \le 200000$, $1 \le M \le 1000000$), where $N$ is the number of intersections and $M$ is the number of lanes. Each of the next $M$ lines contains two integers $i$ and $j$ ($1 \le i, j \le N$) describing a lane between intersections $i$ and $j$. The graph is planar and simple: it can be drawn in the plane so that edges meet only at shared endpoints, and it has no loops and no repeated lanes between the same pair of intersections.

Print a single integer: the smallest possible value, over all ways of orienting every lane, of the maximum number of outgoing streets at any intersection.