Distinct Routes

from collections import deque
#def main():
#    n, target = map(int, input().split())
#    values = list(map(int, input().split()))

#    array = [(value, i + 1) for i, value in enumerate(values)]
#    array.sort()

#    for i in range(n):
#        left = i + 1
#        right = n - 1

#        while left < right:
#            total = array[i][0] + array[left][0] + array[right][0]

#            if total == target:
#                print(array[i][1], array[left][1], array[right][1])
#                return

#            elif total < target:
#                left += 1

#            else:
#                right -= 1

#    print("IMPOSSIBLE")

def ylb():

    used_teleporter = set()

    n, m = list(map(int, input().split()))

    adjacency_list = {}

    for i in range(1, n+1):
        adjacency_list[i] = []

    for _ in range(n):
        a, b = list(map(int, input().split()))

        adjacency_list[a].append(b)
        adjacency_list[b].append(a)

    print(adjacency_list)

    def dfs(node):

        if node in visited:
            return





def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    edges = []

    for _ in range(m):
        a, b = map(int, input().split())
        edges.append((a, len(graph[a])))
        graph[a].append([b, 1, len(graph[b])])
        graph[b].append([a, 0, len(graph[a]) - 1])

    flow = 0

    while True:
        parent = [None] * (n + 1)
        parent[1] = (-1, -1)
        queue = deque([1])

        while queue and parent[n] is None:
            u = queue.popleft()
            for i, (v, cap, rev) in enumerate(graph[u]):
                if cap > 0 and parent[v] is None:
                    parent[v] = (u, i)
                    queue.append(v)

        if parent[n] is None:
            break

        v = n
        while v != 1:
            u, i = parent[v]
            edge = graph[u][i]
            edge[1] -= 1
            graph[v][edge[2]][1] += 1
            v = u

        flow += 1

    used = [[] for _ in range(n + 1)]
    for u, i in edges:
        if graph[u][i][1] == 0:
            used[u].append(graph[u][i][0])

    routes = []
    for _ in range(flow):
        parent = [-1] * (n + 1)
        parent[1] = 1
        queue = deque([1])

        while queue and parent[n] == -1:
            u = queue.popleft()
            for v in used[u]:
                if parent[v] == -1:
                    parent[v] = u
                    queue.append(v)

        route = []
        v = n
        while v != 1:
            route.append(v)
            u = parent[v]
            used[u].remove(v)
            v = u

        route.append(1)
        routes.append(route[::-1])

    print(flow)
    for route in routes:
        print(len(route))
        route = map(str, route)
        print(" ".join(route))

main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED