#P10887. [2015yali备战noi]union
[2015yali备战noi]union
题目描述
有 座城市,由 条道路相连。任意两座城市之间恰有一条路径。初始时每座城市是一个独立的州。
合并分若干轮进行。每轮中,一个州至多和另一个州合并。两个州可以合并,当且仅当有一条道路的两端分别属于这两个州。合并得到的新州包含原先两个州的所有城市。
求将全部城市合并为一个州的最少轮数。
输入格式
第一行一个整数 (),表示数据组数。每组两行:
- 第一行一个整数 (),城市编号为 。
- 第二行 个整数。第 个整数 ()表示城市 与城市 之间有一条道路。
输出格式
每组数据输出一行一个整数,表示最少合并轮数。
样例
3
4
0 1 2
8
0 1 2 0 0 3 3
9
0 1 1 1 1 0 2 2
2
4
5