#1321. [清华集训 2017] 小 Y 和地铁

[清华集训 2017] 小 Y 和地铁

题目描述

小 Y 是一个爱好旅行的 OIer。一天,她来到了一个新的城市。由于不熟悉那里的交通系统,她选择了坐地铁。

她发现每条地铁线路可以看成平面上的一条曲线,不同线路的交点处一定会设有换乘站 。通过调查得知,没有线路是环线,也没有线路与自身相交。任意两条不同的线路只会在若干个点上相交,没有重合的部分,且没有三线共点的情况。即,如图所示的情况都是不存在的:

小 Y 坐着地铁 00 号线,路上依次经过了 nn 个换乘站。她记下了每个换乘站可以换乘的线路编号,发现每条线路与她所乘坐的线路最多只有 22 个换乘站。现在小 Y 想知道,除掉她经过的换乘站以外,这个城市里最少有几个换乘站。只有你告诉她正确的答案,她才会答应下次带你去玩呢。

输入格式

请注意本题有多组输入数据。

输入数据的第一行是一个整数 TT,表示输入数据的组数。接下来依次给出每组数据。

对于每组数据,第一行是一个整数 nn,表示小 Y 经过的换乘站的数目。第二行为 nn 个用空格隔开的整数,依次表示每个换乘站的可以换乘的线路编号。这些编号都在 1∼n1\sim n 之内。

输出格式

对于每组输入数据,输出一行一个整数,表示除掉这 nn 个换乘站之外,最少有几个换乘站。

样例

4 4
1 2 1 2
8
1 2 3 4 1 2 3 4
5
5 4 3 3 5
8
1 2 3 4 1 3 2 4
0 
0 
0 
1

题目来源:洛谷 P4005