One-Way Roads

In the country of Via, roads connect the cities and every road can be driven in both directions. The lanes are not separated, so accidents are common: drivers look at their smartphones while driving and hit the oncoming traffic. The politicians of Via decided to turn every road into a one-way road. Each existing road keeps exactly one of its two possible directions.

The mayors do not want too many one-way roads leading into their cities, because that causes traffic jams inside a city. Find the smallest integer $d$ such that there is an assignment of directions in which every city has at most $d$ one-way roads leading into it.

The first line contains an integer $n$ ($1 \le n \le 500$), the number of cities. The cities are labeled from 1 to $n$.

The second line contains an integer $m$ ($0 \le m \le 2500$), the number of bidirectional roads.

Each of the next $m$ lines describes one road with two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), meaning that there is a road between city $a$ and city $b$.

There is at most one road between any two cities.

Print the minimum $d$ on one line.