Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- A company offers personal computers for sale inNtowns (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 locatedeither 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.
- Input
- The input consists of more than one description of town (but totally, less than ten descriptions). Everydescription starts with number N of towns and number M of pairs of towns directly connected each other. The integers N and M are separated by a space. Every one of the next M rows contains a pair of connected towns, one pair per row. The pair consists of two integers for town's numbers, separated by a space. The input ends with N = 0 and M = 0.
- Output
- For every town in the input write a line containing the obtained minimum.
- Sample Input
- 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
- Sample Output
- 2
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement