C. Между
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$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$$$) — максимально возможное значение элемента последовательности и количество пар.

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$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$$$ включительно, обозначающие элементы последовательности.

Если существует несколько последовательностей с максимальной длиной, выведите любую из них.

Можно доказать, что во всех наборах входных данных с ответом «FINITE», при данных ограничениях, максимально возможная сумма длин последовательностей в этих наборах входных данных не превосходит $$$2\cdot10^6$$$.

Пример
Входные данные
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
Выходные данные
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
Примечание

В первом наборе входных данных есть элемент $$$1$$$ между двумя элементами со значением $$$3$$$, и элемент $$$1$$$ между двумя элементами со значением $$$2$$$. Можно доказать, что не существует подходящих последовательностей длины более $$$5$$$.

Во втором наборе входных данных $$$[1]$$$ является единственной возможной последовательностью, потому что должен быть ровно один элемент со значением $$$1$$$ в последовательности.

В третьем наборе входных данных мы можем получить сколь угодно длинную последовательность вида $$$1, 2, 2, 2, \ldots$$$.