CF1815C.Between

You are given an integer $n$, as well as $m$ pairs of integers $(a_i,b_i)$, where $1\leq a_i , b_i \leq n$, $a_i \ne b_i$.

You want to construct a sequence satisfying the following requirements:

• All elements in the sequence are integers between $1$ and $n$.
• There is exactly one element with value $1$ in the sequence.
• For each $i$ ($1 \le i \le m$), between any two elements (on different positions) in the sequence with value $a_i$, there is at least one element with value $b_i$.
• The sequence constructed has the maximum length among all possible sequences satisfying the above properties.

Sometimes, it is possible that such a sequence can be arbitrarily long, in which case you should output "INFINITE". Otherwise, you should output "FINITE" and the sequence itself. If there are multiple possible constructions that yield the maximum length, output any.

给你一个整数 $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" 及该序列本身。若存在多个可达到最大长度的构造方案，输出任意一个即可。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 300$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 1500$, $0 \le m \le 5000$) — the maximum possible value of the element of the sequence and the number of pairs.

The $i$-th of the next $m$ lines contain two integers $a_i$ and $b_i$ ($1 \le a_i , b_i \le n$, $a_i \ne b_i$).

$(a_i, b_i) \ne (a_j, b_j)$ for all $1 \le i \lt j \le m$.

It is guaranteed that sum of $n$ over all test cases doesn't exceed $1500$ and the sum of $m$ over all test cases doesn't exceed $5000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$）。

对所有满足 $1 \le i \lt j \le m$ 的 $i, j$，均有 $(a_i, b_i) \ne (a_j, b_j)$。

保证所有测试用例的 $n$ 之和不超过 $1500$，且所有测试用例的 $m$ 之和不超过 $5000$。

For each test case, on the first line output "INFINITE" if the sequence can be arbitrarily long, and "FINITE" otherwise.

If you have outputted "FINITE", then your output should be followed by $2$ lines.

The first line contains an integer $s$, the maximum length of the sequence.

The second line contains $s$ integers, each are between $1$ and $n$ inclusive, representing the elements of the sequence.

If there are multiple sequences with the maximum length, output any of them.

It can be shown that, for all test cases with answer "FINITE", then under the constraints, the maximum possible sum of sequence lengths of those test cases does not exceed $2\cdot10^6$.

对于每个测试用例，若序列可以任意长，则在第一行输出 “INFINITE”；否则输出 “FINITE”。

若输出为 “FINITE”，则其后应再输出 $2$ 行：

第一行包含一个整数 $s$，表示序列的最大长度；

第二行包含 $s$ 个整数，每个整数均在 $1$ 到 $n$（含）之间，表示该序列的各元素。

若存在多个具有最大长度的序列，输出其中任意一个即可。

可以证明：对所有答案为 “FINITE” 的测试用例，在给定约束下，这些测试用例的序列最大长度之和不超过 $2\cdot10^6$。

In the first test case, there is an element $1$ between two elements with value $3$ and an element $1$ between two elements with value $2$. It can be shown that there is no suitable sequences of length more than $5$.

In the second case, $[1]$ is the only possible sequence because there should be exactly one element with value $1$ in the sequence.

In the third case, we can get an arbitrary long sequence like $1, 2, 2, 2, \ldots$.

在第一个测试用例中，两个值为 $3$ 的元素之间存在一个值为 $1$ 的元素，且两个值为 $2$ 的元素之间也存在一个值为 $1$ 的元素。可以证明，不存在长度超过 $5$ 的满足条件的序列。

在第二个测试用例中，唯一可能的序列是 $[1]$，因为序列中必须恰好包含一个值为 $1$ 的元素。

在第三个测试用例中，我们可以构造任意长的序列，例如 $1, 2, 2, 2, \ldots$。