Distinct Routes

#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





from collections import deque

def main():

    n, m = map(int, input().split())
    adjacency_list = [[] for _ in range(n + 1)]
    cap = {}
    edges = set()

    for _ in range(m):
        a, b = map(int, input().split())
        adjacency_list[a].append(b)
        adjacency_list[b].append(a)
        cap[a, b] = 1
        cap[b, a] = 0
        edges.add((a, b))

    flow = 0

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

        while queue and parent[n] == -1:
            u = queue.popleft()
            for node in adjacency_list[u]:
                if parent[node] == -1 and cap[u, node] > 0:
                    parent[node] = u
                    queue.append(node)

        if parent[n] == -1:
            break

        node = n
        while node != 1:
            u = parent[node]
            cap[u, node] -= 1
            cap[node, u] += 1
            node = u

        flow += 1

    routes = []
    for _ in range(flow):
        route = [1]
        u = 1



        while u != n:
            for node in adjacency_list[u]:
                
                if (u, node) in edges and cap[u, node] == 0:

                    cap[u, node] += 1
                    cap[node, u] -= 1
                    route.append(node)
                    u = node
                    break
        routes.append(route)

    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: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: ACCEPTED