← 返回题目列表

Codeforces · 1327/B

B. 公主和王子

中文机器翻译题面 查看原题

Berland Polycarp LXXXIV 国王有 $$$n$$$ 个女儿。为了巩固自己对邻国的权力,他想将自己的女儿嫁给这些王国的王子。幸运的是,还有其他王国。

因此,Polycarp LXXXIV 列举了从 $$$1$$$ 到 $$$n$$$ 的女儿们,以及从 $$$1$$$ 到 $$$n$$$ 的王国。他为每个女儿编制了一份她想嫁给的王国王子名单。

波利卡普LXXXIV很忙,于是他贪婪地为女儿们陆续找到了一对。

对于第一个女儿,他从她的列表中选择了编号最低的王国,并将女儿嫁给了他们的王子。对于第二个女儿,他从她的名单中选择了数字最低的王国,其中的王子还没有被夺走。如果名单上没有自由王子,那么女儿就不会与任何人结婚,波利卡普 LXXXIV 会继承下一个女儿。该过程在第 $$$n$$$ 个女儿之后结束。

例如,假设有 $$$4$$$ 个女儿和王国,则女儿的列表分别为 $$$[2, 3]$$$、$$$[1, 2]$$$、$$$[3, 4]$$$、$$$[3]$$$。

在这种情况下,女儿$$$1$$$嫁给了王国王子$$$2$$$,女儿$$$2$$$嫁给了王国王子$$$1$$$,女儿$$$3$$$嫁给了王国王子$$$3$$$,让女儿$$$4$$$无人结婚。

实际上,在开始婚姻程序之前,波利卡普 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”。第二行应该包含两个整数——女儿的索引和 Polycarp LXXXIV 王国的索引应该添加到该女儿的列表中。

如果有多种方法可以添加条目以使已婚夫妇的总数增加,则打印其中任何一种。

否则,唯一的一行应包含一个单词“OPTIMAL”。

示例

输入 #1

5
4
2 2 3
2 1 2
2 3 4
1 3
2
0
0
3
3 1 2 3
3 1 2 3
3 1 2 3
1
1 1
4
1 1
1 2
1 3
1 4

输出 #1

IMPROVE
4 4
IMPROVE
1 1
OPTIMAL
OPTIMAL
OPTIMAL

注意

语句中描述了第一个测试用例。将第四国加入到四女儿的名单中,让她嫁给了第四国的王子。

在第二个测试用例中,任何新条目都会将婚姻数量从 $$$0$$$ 增加到 $$$1$$$。

在第三个和第四个测试用例中,无法添加条目。

在第五个测试用例中,无法通过添加任何条目来更改婚姻。