Missing Bridges#8555
On Fig. 1 a scheme of islands, presented by points and labeled from to , and bridges, presented by lines, each of them connecting different islands, are shown.
Each bridge could be traversed in both directions. The task is to start from some island, to pass on each of the bridges exactly once, and to return at the starting point. Such walk is called all-bridges-walk.
To do this with the islands and bridges on Fig. 1 is impossible. But, if some new bridges are built, then the asked walk could be made – for example with new bridges that connect island with island and island with island . On Fig. 2 a region with four islands and three bridges is shown. If the all-bridges-walk for this region is asked, then two bridges from point to point will be enough for doing the walk.
It is given a country with islands and bridges. Write a program bridges to find the smallest number of bridges to build in order to have an all-bridges-walk in the country.
First line contains the numbers and (n \le 1000, m \le 10000). On each of the next lines the two ends of a bridge will be given.
On the first line print the number of the necessary new bridges. Each of the next lines has to contain the two ends of a new bridge. Any set of new bridges that guaranties all-bridges-walk is acceptable as solution. If new bridges are not necessary, the program has to print just .
Esempio 1
Esempio 2