CF1327B.Princesses and Princes

The King of Berland Polycarp LXXXIV has $n$ daughters. To establish his power to the neighbouring kingdoms he wants to marry his daughters to the princes of these kingdoms. As a lucky coincidence there are $n$ other kingdoms as well.

So Polycarp LXXXIV has enumerated his daughters from $1$ to $n$ and the kingdoms from $1$ to $n$. For each daughter he has compiled a list of kingdoms princes of which she wanted to marry.

Polycarp LXXXIV is very busy, so he finds a couple for his daughters greedily one after another.

For the first daughter he takes the kingdom with the lowest number from her list and marries the daughter to their prince. For the second daughter he takes the kingdom with the lowest number from her list, prince of which hasn't been taken already. If there are no free princes in the list then the daughter marries nobody and Polycarp LXXXIV proceeds to the next daughter. The process ends after the $n$-th daughter.

For example, let there be $4$ daughters and kingdoms, the lists daughters have are $[2, 3]$, $[1, 2]$, $[3, 4]$, $[3]$, respectively.

In that case daughter $1$ marries the prince of kingdom $2$, daughter $2$ marries the prince of kingdom $1$, daughter $3$ marries the prince of kingdom $3$, leaving daughter $4$ nobody to marry to.

Actually, before starting the marriage process Polycarp LXXXIV has the time to convince one of his daughters that some prince is also worth marrying to. Effectively, that means that he can add exactly one kingdom to exactly one of his daughter's list. Note that this kingdom should not be present in the daughter's list.

Polycarp LXXXIV wants to increase the number of married couples.

Unfortunately, what he doesn't have the time for is determining what entry to add. If there is no way to increase the total number of married couples then output that the marriages are already optimal. Otherwise, find such an entry that the total number of married couples increases if Polycarp LXXXIV adds it.

If there are multiple ways to add an entry so that the total number of married couples increases then print any of them.

For your and our convenience you are asked to answer $t$ independent test cases.

伯兰德国王波利卡普·LXXXIV 有 $n$ 个女儿。为了向邻国彰显自己的权势，他希望将女儿们嫁给这些国家的王子。巧合的是，恰好也有 $n$ 个邻国。

因此，波利卡普·LXXXIV 将他的女儿从 $1$ 到 $n$ 编号，也将邻国从 $1$ 到 $n$ 编号。对于每个女儿，他都整理了一份她愿意嫁予其王子的国家列表。

波利卡普·LXXXIV 非常繁忙，因此他采用贪心策略，依次为女儿们安排婚配。

对于第一个女儿，他从她的列表中选择编号最小的国家，并让她嫁给该国的王子；
对于第二个女儿，他从她的列表中选择编号最小、且其王子尚未被选中的国家；
若她的列表中已无可用的王子，则该女儿无法结婚，波利卡普·LXXXIV 继续处理下一个女儿；
该过程持续至第 $n$ 个女儿为止。

例如，假设有 $4$ 个女儿和 $4$ 个国家，各女儿的意愿列表分别为 $[2, 3]$、$[1, 2]$、$[3, 4]$、$[3]$。

在此情况下：女儿 $1$ 嫁给国家 $2$ 的王子，女儿 $2$ 嫁给国家 $1$ 的王子，女儿 $3$ 嫁给国家 $3$ 的王子，而女儿 $4$ 则无人可嫁。

实际上，在正式开始婚配流程之前，波利卡普·LXXXIV 还有时间说服其中一位女儿：某位王子也值得嫁。这等价于——他可以恰好向某一位女儿的意愿列表中添加一个国家（该国家原本不在该女儿的列表中）。

波利卡普·LXXXIV 希望借此提高最终成功配对的夫妻总数。

遗憾的是，他没有时间自行确定应添加哪一项。如果无论如何添加都无法提升配对总数，则输出“婚姻已达到最优”；否则，请找出一个可行的添加项，使得配对总数得以增加。

若存在多种添加方式均可提升配对总数，则输出任意一种即可。

为便于你与我们处理，本题包含 $t$ 组相互独立的测试用例。

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of daughters and the number of kingdoms.

Each of the next $n$ lines contains the description of each daughter's list. The first integer $k$ ($0 \le k \le n$) is the number of entries in the $i$-th daughter's list. After that $k$ distinct integers follow $g_i[1], g_i[2], \dots, g_i[k]$ ($1 \le g_i[j] \le n$) — the indices of the kingdoms in the list in the increasing order ($g_i[1] \lt g_i[2] \lt \dots \lt g_i[k]$).

It's guaranteed that the total number of daughters over all test cases does not exceed $10^5$.

It's also guaranteed that the total number of kingdoms in lists over all test cases does not exceed $10^5$.

第一行包含一个整数 $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] \lt g_i[2] \lt \dots \lt g_i[k]$）。

保证所有测试用例中女儿总数不超过 $10^5$。

同时也保证所有测试用例中偏好列表所含王国总数不超过 $10^5$。

For each test case print the answer to it.

Print "IMPROVE" in the first line if Polycarp LXXXIV can add some kingdom to some of his daughter's list so that the total number of married couples increases. The second line then should contain two integers — the index of the daughter and the index of the kingdom Polycarp LXXXIV should add to that daughter's list.

If there are multiple ways to add an entry so that the total number of married couples increases then print any of them.

Otherwise the only line should contain one word "OPTIMAL".

对每个测试用例，输出其答案。

如果波利卡普·LXXXIV 可以向某位女儿的列表中添加某个王国，从而使已婚夫妇的总数增加，则在第一行输出 "IMPROVE"；第二行应包含两个整数——所选女儿的索引和所添加王国的索引。

如果存在多种方式添加条目以使已婚夫妇总数增加，则输出其中任意一种即可。

否则，仅输出一行，内容为单词 "OPTIMAL"。

The first test case is depicted in the statement. Adding the fourth kingdom to the list of the fourth daughter makes her marry the prince of the fourth kingdom.

In the second test case any new entry will increase the number of marriages from $0$ to $1$.

In the third and the fourth test cases there is no way to add an entry.

In the fifth test case there is no way to change the marriages by adding any entry.

第一个测试用例如题面图示所示。将第四个王国加入第四个女儿的列表后，她便会嫁给第四个王国的王子。

在第二个测试用例中，任意新增条目都会使婚姻数从 $0$ 增加到 $1$。

在第三个和第四个测试用例中，不存在任何可行的新增条目方式。

在第五个测试用例中，无论添加何种条目，都无法改变当前的婚姻匹配情况。