1721 - Smooth Project
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 85
Solved: 39
- Description
A government got the existing urban road statistics table, the table lists each road directly connected to the town by investigating the urban traffic conditions. The goal of the "smooth project" of the provincial government is to enable traffic between the each two towns of the (But not necessarily directly connected to each other, as long as they can achieve each other extra). Question: At least how many roads do you need to build?
- Input
The test input contains several test cases. The first row of each test case gives two positive integers, namely the number of towns N (<1000) and the number of roads M; the subsequent M rows match the M roads, and each of them give a pair of positive integers which are the numberings of the two towns directly connected by the road. For simplicity, towns are numbered from 1 to n.
Note: There are multiple roads between the two cities, that is to say
3 3
1 2
1 2
2 1
This input is also legal
When N is 0, the input ends and the use case is not processed.
- Output
For each test case, output it in one line of the number of roads that need to be built at least.
- sample input
-
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0
- sample output
-
1 0 2 998
- hint
- source