In the country of Via, the cities are connected by roads that can be used in both directions. However, this has been the cause of many accidents since the lanes are not separated: The drivers frequently look at their smartphones while driving, causing them to collide with the oncoming traffic. To alleviate the problem, the politicians of Via came up with the magnificent idea to have one-way roads only, i.e., the existing roads are altered such that each can be only used in one of two possible directions. They call this "one-way-ification".
The mayors do not want too many one-way roads to lead to their cities because this can cause traffic jam within the city: they demand that the smallest integer be found such that there is a 'one-way-ification' in which for every city, the number of one-way roads leading to it is at most .
The first line contains the number of cities from to .
The second line contains the number of bi-directional roads .
Each of the next lines contains two integers and indicating a road between cities and .
There is at most one road between two cities.
Output the minimum number .