SP22529 DANDVIOL - Dandiya Night and Violence

现在是达尼亚舞之夜！我们来看看达尼亚舞的玩法： 共有 **N** 对人在跳舞。这一对中的两个人会互相跳达尼亚舞。由于长时间和同一个舞伴跳舞可能会让人感到无聊，因此一个人可以选择与其他对中的朋友交换舞伴。例如，原本的配对是 (1, 2) 和 (3, 4)，如果 1 和 3 是朋友，他们可以交换舞伴，结果配对可能变成 (3, 2) 和 (1, 4)。友谊关系是传递的，这意味着如果 (x, y) 和 (y, z) 是朋友，那么 (x, z) 也是朋友。 然而，达尼亚舞的舞棍如果使用不当，可能会发生危险。有些舞伴间不友好，他们可能会进行激烈的对抗。当一对舞伴 (5, 6) 互为敌人（不是朋友）时，就会发生激烈的达尼亚舞对抗。ACM 在达尼亚舞之夜对这种情况表示了关注。 现在，根据初始配对信息，请帮助我们计算出在整场达尼亚舞之夜中，可能发生的最大激烈达尼亚舞对抗次数。 **注意：** 配对 (x, y) 是无序的，即 (x, y) 和 (y, x) 应被视为相同的配对。

第一行输入一个整数 $T$，表示测试用例的数量。 接下来是 $T$ 个测试用例，每个用例如下： - 第一行输入两个整数 $N$ 和 $F$，分别表示配对数量和朋友对的数量。 - 接下来 $N$ 行，每行有两个整数，表示一个初始配对（人们编号从 1 到 $2N$）。 - 然后接下来 $F$ 行，每行有两个整数，表示一对朋友。

对于每个测试用例，输出一个整数，表示可能达到的最大激烈达尼亚舞对抗次数。

- $T \leq 100$ - $1 \leq N \leq 200$ - $0 \leq F \leq \min(5000, C(2N, 2))$，其中 $C(n, k)$ 表示二项式系数。 **本翻译由 AI 自动生成**