SP13683 TRANCLS - Transitive Closure

在数学中，如果集合 $S$ 满足这样一个条件：当元素 $a$ 与元素 $b$ 相关，且元素 $b$ 与元素 $c$ 相关时， $a$ 必须与 $c$ 相关，那么这个集合 $S$ 就是传递的。换句话说，集合中的所有对 $(a, b)$ 和 $(b, c)$ 存在时，必然也存在对 $(a, c)$。 举个例子，集合 $S = \{ (1,2), (2,3), (3,4), (2,4) \}$。这个集合是传递关系吗？答案是否定的，因为存在 $(1,2)$ 和 $(2,3)$ 却缺少 $(1,3)$。如果我们添加 $(1,3)$，集合会变得传递吗？更新后的集合为 $S = \{ (1,2), (2,3), (3,4), (2,4), (1,3) \}$。仍然不是，因为存在 $(1,3)$ 和 $(3,4)$ 却缺少 $(1,4)$。若再添加 $(1,4)$，集合会是传递的吗？更新后的集合为 $S = \{ (1,2), (2,3), (3,4), (2,4), (1,3), (1,4) \}$。此时集合 $S$ 是传递的，因为我们添加了两对：$(1,3)$ 和 $(1,4)$。这两对称为传递闭包（即将集合 $S$ 变为传递集的最小附加对）。你的任务是，给定集合 $S$，输出需要添加的最少附加对数使集合成为传递关系。

输入的第一行为整数 $T$（$0 < T \leq 100$），表示测试用例的数量。每个测试用例的第一行是整数 $N$（$0 < N \leq 100$），表示集合中的对数，接下来是 $N$ 行，每行包含一对整数 $(a, b)$（$0 \leq a, b < N$）。

对于每个测试用例，输出一行 "Case #i: X"，其中 "i" 是测试用例编号（从 1 开始），"X" 是需要添加的最少对数使集合成为传递关系。每个测试用例的结果应单独占一行。 **本翻译由 AI 自动生成**