P14219 [ICPC 2024 Kunming I] 阻止城堡 2

一块有 $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$ 座城堡。 :::align{center}  ::: 对于第三组样例数据，由于只有 $1$ 座城堡，不存在可以互相攻击的城堡对。