Bytie is playing the computer game Tower Defense. His aim is to construct guard towers, so that they protect all of his domain. There are multiple towns in Bytie's domain, some of which are linked by bidirectional roads. If Bytie erects a guard tower in a city, then the tower protects its city and all the cities directly linked with it by roads.
Just as Bytie was pondering over the placement of guard towers in his domain, his elder sister Bytea entered the room. She glanced at the map displayed on the screen, and after a moment exclaimed: "Oi, what is there to think about, clearly K towers suffice!".
Angered by his sister spoiling the fun, Bytie showed his sister the door, and began wondering what to do next. Pride will not let him construct more than K towers. He has an up his sleeve though: he can research a technology that will allow him to constructimproved guard towers. An improved guard tower protects not only the town it was erected in and its immediate neighbors but also the towns that are further away. Formally, an improved guard tower built in the town U protects the town V if either of the following holds:
there is a direct road from U to V ;
or there is such a town W that there are direct roads from U to W and from W to V.
Of course, Bytie still strives to erect at most K towers, but he has no qualms about making these the improved guard towers.
The towns in Bytie's domain are numbered from 1 to N. Next, M lines describing the roads follow. Each of those lines holds two integers, Ai and Bi (1<=Ai,Bi<=N,Ai<>Bi) , indicating that the towns no. Ai and Bi are directly linked by a bidirectional road. Each pair of towns is linked by at most a single road.
If more than one solution exists, any solution can be printed. Let us remind that any placement of no more than K improved towers will do - you need not minimize their number. You may assume that Bytea was correct, i.e., that the whole domain of Bytie can indeed be protected by K plain (not improved) guard towers. Thus a solution always exists.
9 8 3
1 5 7