Between (Codeforces 1815C)
Tags: Greedy, dfs and similar

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

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

Sample Inputs:
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

Sample Outputs:
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

Solution (Python):
from collections import deque
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    for i in range(m):
        (a, b) = list(map(int, input().split()))
        graph[b].append(a)
    dist = [[] for _ in range(n)]
    queue = deque([1])
    d = [-1] * (n + 1)
    d[1] = 0
    while queue:
        x = queue.popleft()
        dist[d[x]].append(x)
        for i in graph[x]:
            if d[i] == -1:
                d[i] = d[x] + 1
                queue.append(i)
    if min(d[1:]) == -1:
        print('INFINITE')
    else:
        print('FINITE')
        ans = []
        m = max(d)
        for i in range(m, -1, -1):
            for j in range(i, m + 1, 2):
                ans += dist[j]
        for i in range(1, m + 1):
            for j in range(i, m + 1, 2):
                ans += dist[j]
        print(len(ans))
        print(*ans)

Solution (Python):
from collections import deque
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    for i in range(m):
        (a, b) = list(map(int, input().split()))
        graph[b].append(a)
    dist = [[] for _ in range(n)]
    queue = deque([1])
    d = [-1] * (n + 1)
    d[1] = 0
    while queue:
        x = queue.popleft()
        dist[d[x]].append(x)
        for i in graph[x]:
            if d[i] == -1:
                d[i] = d[x] + 1
                queue.append(i)
    if min(d[1:]) == -1:
        print('INFINITE')
    else:
        print('FINITE')
        ans = []
        m = max(d)
        for i in range(m, -1, -1):
            for j in range(i, m + 1, 2):
                ans += dist[j]
        for i in range(1, m + 1):
            for j in range(i, m + 1, 2):
                ans += dist[j]
        print(len(ans))
        print(*ans)

Solution (Python):
""""""

def get_depth_sequence(max_d):
    depth_sequence = []
    for left in range(max_d, 0, -1):
        for i in range(left, max_d + 1):
            depth_sequence.append(i)
    return depth_sequence

def solve(n, m, edges):
    adj = [[] for _ in range(n + 1)]
    for (a, b) in edges:
        if a == 1:
            continue
        adj[b].append(a)
    depth = [-1] * (n + 1)
    depth[1] = 1
    q = [1]
    max_d = 1
    while q:
        q2 = []
        for u in q:
            max_d = max(max_d, depth[u])
            for v in adj[u]:
                if depth[v] == -1:
                    depth[v] = depth[u] + 1
                    q2.append(v)
        q = q2
    INFINITE = False
    for u in range(1, n + 1):
        if depth[u] == -1:
            INFINITE = True
    if INFINITE:
        return [['INFINITE']]
    ans = [['FINITE']]
    depth_elements = [[] for __ in range(max_d + 1)]
    for u in range(1, n + 1):
        depth_elements[depth[u]].append(u)
    ans_arr = []
    for d in get_depth_sequence(max_d):
        for u in depth_elements[d]:
            ans_arr.append(u)
    ans.append([len(ans_arr)])
    ans.append(ans_arr)
    return ans

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        edges = []
        for __ in range(m):
            (a, b) = readIntArr()
            edges.append([a, b])
        ans = solve(n, m, edges)
        allans.extend(ans)
    multiLineArrayOfArraysPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()