310321: CF1815C. Between

C. Betweentime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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 < 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$.

Output

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$.

ExampleInput

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

Output

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 

Note

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$.

题目大意：
给定一个整数n，以及m对整数(ai,bi)，其中1≤ai,bi≤n，ai≠bi。要求构造一个序列满足以下条件：
1. 序列中的所有元素都是介于1和n之间的整数。
2. 序列中恰好有一个值为1的元素。
3. 对于每个i（1≤i≤m），在序列中任意两个值为ai的元素之间，至少有一个值为bi的元素。
4. 构造的序列在满足上述性质的所有可能序列中长度最大。

有时可能存在可以任意长的序列，此时应输出“INFINITE”。否则，应输出“FINITE”和序列本身。如果有多个可能构造的序列长度相同，则输出其中任意一个。

输入数据格式：
每个测试用例包含多个测试案例。第一行包含一个整数t（1≤t≤300），表示测试案例的数量。接下来是每个测试案例的描述。
每个测试案例的第一行包含两个整数n和m（1≤n≤1500，0≤m≤5000），分别表示序列中元素的最大可能值和整数对的数量。
接下来的m行，每行包含两个整数ai和bi（1≤ai,bi≤n，ai≠bi）。
保证所有测试案例的n之和不超过1500，m之和不超过5000。

输出数据格式：
对于每个测试案例，如果序列可以任意长，则第一行输出“INFINITE”；否则输出“FINITE”。
如果输出“FINITE”，则接下来输出两行：
第一行包含一个整数s，表示序列的最大长度。
第二行包含s个整数，每个数都在1到n之间，表示序列的元素。
如果有多个长度最大的序列，则输出其中任意一个。
可以证明，对于所有答案为“FINITE”的测试案例，在约束条件下，这些测试案例的序列长度之和不超过2×10^6。题目大意： 给定一个整数n，以及m对整数(ai,bi)，其中1≤ai,bi≤n，ai≠bi。要求构造一个序列满足以下条件： 1. 序列中的所有元素都是介于1和n之间的整数。 2. 序列中恰好有一个值为1的元素。 3. 对于每个i（1≤i≤m），在序列中任意两个值为ai的元素之间，至少有一个值为bi的元素。 4. 构造的序列在满足上述性质的所有可能序列中长度最大。 有时可能存在可以任意长的序列，此时应输出“INFINITE”。否则，应输出“FINITE”和序列本身。如果有多个可能构造的序列长度相同，则输出其中任意一个。 输入数据格式： 每个测试用例包含多个测试案例。第一行包含一个整数t（1≤t≤300），表示测试案例的数量。接下来是每个测试案例的描述。 每个测试案例的第一行包含两个整数n和m（1≤n≤1500，0≤m≤5000），分别表示序列中元素的最大可能值和整数对的数量。 接下来的m行，每行包含两个整数ai和bi（1≤ai,bi≤n，ai≠bi）。 保证所有测试案例的n之和不超过1500，m之和不超过5000。 输出数据格式： 对于每个测试案例，如果序列可以任意长，则第一行输出“INFINITE”；否则输出“FINITE”。 如果输出“FINITE”，则接下来输出两行： 第一行包含一个整数s，表示序列的最大长度。 第二行包含s个整数，每个数都在1到n之间，表示序列的元素。 如果有多个长度最大的序列，则输出其中任意一个。 可以证明，对于所有答案为“FINITE”的测试案例，在约束条件下，这些测试案例的序列长度之和不超过2×10^6。