CF1327B Princesses and Princes

伯兰王国的国王 Polycarp LXXXIV 有 $n$ 个女儿。为了向邻国展示自己的权威，他希望将女儿们嫁给这些邻国的王子。幸运的是，正好也有 $n$ 个其他王国。 因此，Polycarp LXXXIV 给他的女儿们编号为 $1$ 到 $n$，并将王国编号为 $1$ 到 $n$。对于每个女儿，他都整理了一份她希望嫁给哪些王子（即哪些王国王子）的名单。 Polycarp LXXXIV 非常忙碌，因此他采用贪心的方式依次为女儿们安排婚姻。 对于第一个女儿，他从她的名单中选择编号最小的王国，将她嫁给该王国的王子。对于第二个女儿，他从她的名单中选择编号最小且该王子的王国还未被选中的王国。如果名单中没有未被选中的王子，则该女儿无人可嫁，Polycarp LXXXIV 继续为下一个女儿安排。这个过程一直持续到第 $n$ 个女儿。 例如，假设有 $4$ 个女儿和 $4$ 个王国，女儿们的名单分别为 $[2, 3]$，$[1, 2]$，$[3, 4]$，$[3]$。 在这种情况下，第 $1$ 个女儿嫁给了第 $2$ 个王国的王子，第 $2$ 个女儿嫁给了第 $1$ 个王国的王子，第 $3$ 个女儿嫁给了第 $3$ 个王国的王子，第 $4$ 个女儿无人可嫁。 实际上，在开始安排婚姻之前，Polycarp LXXXIV 有时间说服其中一位女儿，让她觉得某个王子也值得嫁。也就是说，他可以在某一位女儿的名单中额外添加一个王国。注意，这个王国不能已经在该女儿的名单中。 Polycarp LXXXIV 希望通过这种方式增加已婚配对的数量。 但他没有时间去确定具体应该添加哪一项。如果无法通过添加一项来增加已婚配对的总数，则输出婚姻已经最优。否则，请找出这样的一项，使得如果 Polycarp LXXXIV 添加了它，已婚配对的总数会增加。 如果有多种添加方式都能增加已婚配对的总数，输出任意一种即可。 为了方便你和我们，你需要回答 $t$ 个独立的测试用例。

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 接下来是 $t$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示女儿和王国的数量。 接下来的 $n$ 行，每行描述一位女儿的名单。第一个整数 $k$（$0 \le k \le n$）表示第 $i$ 位女儿名单中的王国数量。接下来有 $k$ 个不同的整数 $g_i[1], g_i[2], \dots, g_i[k]$（$1 \le g_i[j] \le n$），表示名单中王国的编号，且递增排列（$g_i[1] < g_i[2] < \dots < g_i[k]$）。 保证所有测试用例中女儿的总数不超过 $10^5$。 保证所有测试用例中名单中出现的王国总数不超过 $10^5$。

对于每个测试用例，输出对应的答案。 如果 Polycarp LXXXIV 可以通过在某位女儿的名单中添加某个王国来增加已婚配对的总数，第一行输出 "IMPROVE"。第二行输出两个整数，分别表示女儿的编号和应添加的王国编号。 如果有多种添加方式都能增加已婚配对的总数，输出任意一种即可。 否则，只需输出一行 "OPTIMAL"。

第一个测试用例如题面所示。如果将第 $4$ 个王国添加到第 $4$ 位女儿的名单中，她就可以嫁给第 $4$ 个王国的王子。 第二个测试用例中，任意添加一项都能将已婚配对数从 $0$ 增加到 $1$。 第三和第四个测试用例中，无法通过添加任何项来增加已婚配对数。 第五个测试用例中，添加任何项都无法改变已婚配对数。 由 ChatGPT 4.1 翻译