给定一个整数 $$$n$$$,以及 $$$m$$$ 整数对 $$$(a_i,b_i)$$$,其中 $$$1\leq a_i 、 b_i \leq n$$$、$$$a_i \ne b_i$$$。
您想要构造一个满足以下要求的序列:
- 序列中的所有元素都是 $$$1$$$ 和 $$$n$$$ 之间的整数。
- 序列中只有一个值为 $$$1$$$ 的元素。
- 对于每个 $$$i$$$ ($$$1 \le i \le m$$$),在值为 $$$a_i$$$ 的序列中的任意两个元素(位于不同位置)之间,至少有一个值为 $$$b_i$$$ 的元素。
- 构造的序列在满足上述属性的所有可能序列中具有最大长度。
有时,这样的序列可能是任意长,在这种情况下你应该输出“INFINITE”。否则,您应该输出“FINITE”和序列本身。如果有多种可能的结构可以产生最大长度,则输出任何一个。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 300$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 1500$$$, $$$0 \le m \le 5000$$$) — 序列元素的最大可能值和对的数量。
接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i , b_i \le n$$$, $$$a_i \ne b_i$$$)。
$$$(a_i, b_i) \ne (a_j, b_j)$$$ 对于所有 $$$1 \le i < j \le m$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1500$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,如果序列可以任意长,则在第一行输出“INFINITE”,否则输出“FINITE”。
如果您输出了“FINITE”,那么您的输出后面应该是 $$$2$$$ 行。
第一行包含一个整数$$$s$$$,即序列的最大长度。
第二行包含 $$$s$$$ 整数,每个整数都在 $$$1$$$ 和 $$$n$$$ 之间(包括 $$$1$$$ 和 $$$n$$$),表示序列的元素。
如果存在多个具有最大长度的序列,则输出其中任意一个。
可以证明,对于所有答案为“FINITE”的测试用例,那么在约束条件下,这些测试用例的序列长度的最大可能总和不超过$$$2\cdot10^6$$$。
示例
输入 #1
5 3 2 3 1 2 1 1 0 2 0 2 2 1 2 2 1 5 5 2 1 3 1 4 2 4 5 5 1
输出 #1
FINITE 5 2 3 1 2 3 FINITE 1 1 INFINITE FINITE 3 2 1 2 FINITE 10 4 2 3 5 4 1 3 2 5 4
注意
在第一个测试用例中,两个值为 $$$3$$$ 的元素之间有一个元素 $$$1$$$,两个值为 $$$2$$$ 的元素之间有一个元素 $$$1$$$。可以证明,不存在长度超过$$$5$$$的合适序列。
在第二种情况下,$$$[1]$$$ 是唯一可能的序列,因为序列中应该只有一个值为 $$$1$$$ 的元素。
在第三种情况下,我们可以获得任意长序列,例如 $$$1, 2, 2, 2, \ldots$$$。