SP10647 MYQ9 - Divide And Conquer

Thuvax 国王计划征服邻国硅谷。为了做到这一点，他必须逐一攻占每个城市。国王总是强调完备计划，得知唯有在入侵前切断一个城市与其他城市的通信才能成功。他通过间谍获取了城市之间的通信网络信息。这名间谍从硅谷还是一个小城市之初就驻扎在那里，记录了新建城市如何与其他城市建立通信联系。间谍的情报分为三种通信方式。 每个城市只能通过另一座城市来建立通信联系，可用以下三种方式： 1. **类型 1**：与某个城市 $c$ 建立单一的通信链接。 2. **类型 2**：与所有正在与城市 $c$ 通信的城市建立链接，但不能直接与 $c$ 通信。 3. **类型 3**：不仅与城市 $c$ 通信，还与所有正在与 $c$ 通信的城市建立链接。 所有通信路径均为双向。国王得知，在这样的通信网络中，无法以传统方式成功入侵硅谷，于是雇佣恐怖分子协助炸毁部分城市，以便切断关键通信线路。然而，恐怖分子提出要价高昂。因此，请你帮助国王计算出需要炸毁的最少城市数量，从而使他实现对硅谷的征服。

第一行是测试用例的数量 $t$（$1 \le t \le 10$）。 每个测试用例的第一行是硅谷的城市数量 $n$（$1 \le n \le 10^4$）。 接下来的 $n-1$ 行每行包含两个整数 $x$ 和 $c$，表示第 $i+1$ 个城市通过类型 $x$ 的通信方式与城市 $c$ 连接（$1 \le c \le i$）（最初，国家仅有城市 1）。

对于每个测试用例，输出一行，显示国王成功征服国家所需的最少炸毁城市数量。 **本翻译由 AI 自动生成**