题目描述

有一个古老的石头游戏，在任意通用树$T$上进行。目标是按照以下规则在树的根节点放置一个石头：

游戏开始时，玩家选择$K$个石头并将它们全部放入一个桶中。 每一步，玩家可以从桶中取出一个石头，放置在任意一个空的叶子节点上。 当节点$p$的所有$r$个直接子节点都各有一个石头时，玩家可以移除这$r$个石头，将其中一个石头放在$p$上，剩下的$r-1$个石头放回桶中供后续步骤使用。

如果玩家按照上述规则成功在根节点放置一个石头，则游戏胜利。

你需要编写一个程序，确定在给定的输入树中，玩家为了获胜，在游戏开始时最少需要选择的石头数$K$。

输入

输入描述了多个树。文件的第一行是$M$，表示树的数量（$1 \leq M \leq 10$）。接下来是$M$棵树的描述。每棵树有$N < 200$个节点，标号为$1, 2, ..., N$，根节点标号为$1$。每棵树的描述以$N$开头，随后的$N$行按节点标号顺序描述所有节点的子节点。每行包含一个节点标号$p$，其直接子节点的数量$r$，以及$r$个子节点的标号。

输出

对每棵输入树，输出一行表示在步骤1中需要选择的最小石头数，以便在该树上赢得游戏。

输入数据 1

2
7
1 2 2 3
2 2 5 4
3 2 6 7
4 0
5 0
6 0
7 0
12
1 3 2 3 4
2 0
3 2 5 6
4 3 7 8 9
5 3 10 11 12
6 0
7 0
8 0
9 0
10 0
11 0
12 0

输出数据 1

3
4

来源

德黑兰1999竞赛