← 返回题目列表

Codeforces · 1815/C

C. 之间

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

给定一个整数 $$$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$$$。