村村通

题目描述

某市统计了城镇交通状况，得到一份双向道路清单。清单中的每条记录表示两座城镇之间的一条直接相连的道路。 政府计划实施"村村通工程"：通过新建尽可能少的道路，使任意两座城镇之间都能通过若干条道路互相到达（不要求直接相连，只需可达）。

请计算：最少还需新建多少条道路。

输入格式

输入包含若干组测试数据。

• 每组数据的第一行给出两个正整数 \(n\)、\(m\)（分别表示城镇数与现有道路数）。
• 接下来 \(m\) 行，每行给出两个整数，表示一条直接相连的两座城镇的编号（城镇从 \(1\) 到 \(n\) 编号）。
• 同一对城镇之间可能存在多条道路（允许重边）。
• 输入以单独一行 0 结束（表示没有更多测试数据）。

输出格式

对每组数据输出一行，一个整数，表示最少需要新建的道路条数。

输入样例

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

输出样例

1
0
2
998

说明与提示

• 数据范围：\(1 \le n < 1000\)。
• 将城镇与道路视为无向图的点与边；目标是使整张图变为连通图。
• 思考要点：最少新增道路数 = 连通分量数 - 1。