Вам дано целое число \(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» и саму последовательность. Если существует несколько возможных последовательностей с максимальной длиной, выведите любую из них.
Выходные данные
Для каждого набора входных данных на первой строке выведите «INFINITE», если последовательность может быть сколь угодно длинной, и «FINITE» иначе.
Если вы вывели «FINITE», то ваш вывод должен содержать ещё \(2\) строки.
Первая строка содержит целое число \(s\) — максимальную длину последовательности.
Вторая строка содержит \(s\) целых чисел, каждое со значением от \(1\) до \(n\) включительно, обозначающие элементы последовательности.
Если существует несколько последовательностей с максимальной длиной, выведите любую из них.
Можно доказать, что во всех наборах входных данных с ответом «FINITE», при данных ограничениях, максимально возможная сумма длин последовательностей в этих наборах входных данных не превосходит \(2\cdot10^6\).
Примечание
В первом наборе входных данных есть элемент \(1\) между двумя элементами со значением \(3\), и элемент \(1\) между двумя элементами со значением \(2\). Можно доказать, что не существует подходящих последовательностей длины более \(5\).
Во втором наборе входных данных \([1]\) является единственной возможной последовательностью, потому что должен быть ровно один элемент со значением \(1\) в последовательности.
В третьем наборе входных данных мы можем получить сколь угодно длинную последовательность вида \(1, 2, 2, 2, \ldots\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|