A company offers personal computers for sale in N towns (3 <= N <= 35). The towns are denoted by 1, 2, ..., N. There are direct routes connecting M pairs from among these towns. The company decides to build servicing stations in several towns, so that for any town X, there would be a station located either in X or in some immediately neighbouring town of X.
Write a program for finding out the minumum number of stations, which the company has to build, so that the above condition holds.
InputInput:
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5
6
6 7
6 8
0 0
Output:
2