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 d 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 d.
The input consists of:
There is at most one road between two cities.
Output the minimum number d.
2 1 1 2
4 5 1 2 1 3 2 3 2 4 3 4