The amusement park is a real landscape park which means that there are significant portions of forest standing among the attractions. A huge treetop walkway allows the visitors to explore the unusual world of tree canopies and enjoy spectacular views of hills and lakes in the region.
The walkway consists of wooden platforms installed close to the treetops in different heights above the ground and connected by narrow wooden paths. Each path connects exactly two platforms. Number of paths connected to one platform may vary. Each platform can be reached from any other platform without leaving the walkway.
To improve the safety standards and to alleviate occasional bottleneck problems in some parts of the walkway, the management decided to make all paths strictly one-way for the visitors. After each path was assigned a direction, someone found out that a connection problem appeared. It turned out that there may be platforms which would not be accessible from some other platforms if the visitors followed only prescribed path directions and did not leave the walkway. As the direction choice was made by the management on the basis of various "aesthetical and functional considerations", changing the already assigned directions is not an option.
To fix the problem, it was decided to build additional one-way paths. Those will connect selected platforms in such a manner that any platform will be accessible from any other platform without leaving the walkway. All other properties of the walkway will remain unchanged. They are not going to build any new platform.
They want to minimize the number of new paths by careful selection of the platforms to be connected and also by correct direction settings of the new paths.
Input Specification
There are more test cases. Each case starts with a line containing two integers
Output Specification
For each test case, first print a single line with a single integer
Sample Input
5 6
1 2
2 3
3 1
2 4
4 5
5 4
4 3
2 1
3 1
4 1
6 5
1 4
1 5
1 6
2 4
3 4
Sample Output
1
4 1
3
4 2
3 4
1 3
3
4 1
6 2
5 3
Comments