30094 - 阻止城堡II

一块有 10^9 行和 10^9 列的棋盘上放着 n 座城堡与 m 个障碍物。每座城堡或每个障碍物恰好占据一个格子，且被占据的格子两两不同。两座城堡可以互相攻击，若它们位于同一行或同一列，且它们之间没有障碍物或其它城堡。更正式地，令 (i, j) 表示位于第 i 行第 j 列的格子，位于 (i_1, j_1) 和 (i_2, j_2) 的两座城堡可以互相攻击，若以下条件中有一条成立：

• i_1 = i_2，且对于所有 \min(j_1, j_2) < j < \max(j_1, j_2)，不存在位于 (i_1, j) 的障碍物或城堡。
• j_1 = j_2，且对于所有 \min(i_1, i_2) < i < \max(i_1, i_2)，不存在位于 (i, j_1) 的障碍物或城堡。

您需要从棋盘上移除 k 个障碍物，但您不希望太多城堡可以互相攻击。从棋盘上移除恰好 k 个障碍物之后，最小化可以互相攻击的城堡对数。

有多组测试数据。第一行输入一个整数 T 表示测试数据组数，对于每组测试数据：

第一行输入三个整数 n，m 和 k（1 \le n, m \le 10^5，1 \le k \le m）表示城堡的数量，障碍物的数量，以及您需要移除的障碍物的数量。

对于接下来 n 行，第 i 行输入两个整数 r_i 和 c_i（1 \le r_i, c_i \le 10^9），表示第 i 座城堡位于第 r_i 行第 c_i 列。

对于接下来 m 行，第 i 行输入两个整数 r'_i 和 c'_i（1 \le r'_i, c'_i \le 10^9），表示第 i 个障碍物位于第 r'_i 行第 c'_i 列。

保证被占据的格子两两不同。同时保证所有数据 n 之和与 m 之和均不超过 10^5。

每组数据首先输出一行一个整数，表示恰好移除 k 个障碍物之后，最少有几对城堡可以互相攻击。接下来输出一行 k 个不同的由单个空格分隔的整数 b_1, b_2, \cdots, b_k（1 \le b_i \le m），表示您移除的障碍物的编号。如果有多种合法答案，您可以输出任意一种。

对于第一组样例数据，左边的图片展示了原本的棋盘，右边的图片展示了移除 4 个障碍物之后的棋盘。在移除障碍物之后，可以互相攻击的城堡对有：第 2 和第 4 座城堡，第 4 和第 6 座城堡，第 6 和第 7 座城堡，第 7 和第 8 座城堡。 对于第三组样例数据，由于只有 1 座城堡，不存在可以互相攻击的城堡对。