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$$$。
在第三个和第四个测试用例中,无法添加条目。
在第五个测试用例中,无法通过添加任何条目来更改婚姻。