A6398 | $「清华集训 2017」小 Y 和地铁$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

小 Y 是一个爱好旅行的 OIer。一天，她来到了一个新的城市。由于不熟悉那里的交通系统，她选择了坐地铁。 她发现每条地铁线路可以看成平面上的一条曲线，不同线路的交点处一定会设有换乘站![interchange-station.png](/uploads/acgo/image/9601e12261f4a0db_7e06373f4a83.png)。通过调查得知，没有线路是环线，也没有线路与自身相交。任意两条不同的线路只会在若干个点上相交，没有重合的部分，且没有三线共点的情况。即，如图所示的情况都是不存在的：![examples.png](/uploads/acgo/image/a45e76fa127c8872_e1a59cadb731.png) 小 Y 坐着地铁 $0$ 号线，路上依次经过了 $n$ 个换乘站。她记下了每个换乘站可以换乘的线路编号，发现每条线路与她所乘坐的线路最多只有 $2$ 个换乘站。现在小Y想知道，除掉她经过的换乘站以外，这个城市里最少有几个换乘站。只有你告诉她正确的答案，她才会答应下次带你去玩呢。

**请注意本题有多组输入数据。** 输入数据的第一行是一个整数 $T$，表示输入数据的组数。接下来依次给出每组数据。 对于每组数据，第一行是一个整数 $n$，表示小Y经过的换乘站的数目。第二行为 $n$ 个用空格隔开的整数，依次表示每个换乘站的可以换乘的线路编号。这些编号都在 $1$ ~ $n$ 之内。

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

输入 #1

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

输出 #1

C++ 编辑器

输入

输出