CF2046E2 Cheops and a Contest (Hard Version)

这是该问题的困难版本。不同之处在于本版本中 $m$ 可以为任意值。只有在你解决了所有版本的问题后，才能 hack。 古埃及正在举行一场解题比赛，有 $n$ 名参赛者，编号从 $1$ 到 $n$。每位参赛者来自某个城市，城市编号从 $1$ 到 $m$。每个城市至少有一名参赛者。 第 $i$ 位参赛者有力量 $a_i$、专长 $s_i$ 和智慧 $b_i$，满足 $b_i \ge a_i$。比赛中的每道题目都有难度 $d$ 和唯一的话题 $t$。第 $i$ 位参赛者会解出这道题目，当且仅当： - $a_i \ge d$，即他的力量不小于题目的难度，或者 - $s_i = t$ 且 $b_i \ge d$，即他的专长与题目的话题相同，且智慧不小于题目的难度。 Cheops 想要选择题目，使得对于所有 $i < j$，来自城市 $i$ 的每位参赛者解出的题目数量都严格多于来自城市 $j$ 的每位参赛者。 请你找出最多 $5n$ 道题目的集合，使得所有题目的话题互不相同，并满足 Cheops 的要求；或者说明这是不可能的。

每个测试点包含多组测试数据。第一行包含测试组数 $T$（$1 \le T \le 10^4$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $m$（$2 \le m \le n \le 3 \cdot 10^5$），表示参赛者人数和城市数量。 接下来的 $n$ 行描述参赛者。第 $i$ 行包含三个整数 $a_i$、$b_i$、$s_i$（$0 \le a_i, b_i, s_i \le 10^9$，$a_i \le b_i$），分别表示力量、智慧和专长。 接下来的 $m$ 行描述城市。第 $i$ 行的第一个数是整数 $k_i$（$1 \le k_i \le n$），表示第 $i$ 个城市的参赛者人数。接下来是 $k_i$ 个整数 $q_{i,1}, q_{i,2}, \ldots, q_{i,k_i}$（$1 \le q_{i,j} \le n$，$1 \le j \le k_i$），表示该城市参赛者的编号。保证每个参赛者恰好出现一次。 保证所有测试数据中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每组测试数据，如果存在满足 Cheops 要求的题目集合，则第一行输出一个整数 $p$（$1 \le p \le 5n$），表示你选择的题目数量。 接下来 $p$ 行，每行两个整数 $d$ 和 $t$（$0 \le d, t \le 10^9$），分别表示该题目的难度和话题。所有题目的话题必须互不相同。 如果不存在满足 Cheops 要求的题目集合，输出 $-1$。

由 ChatGPT 4.1 翻译