Distinct Routes

import sys
from collections import deque

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    n = int(data[0])
    m = int(data[1])

    adj = [[] for _ in range(n + 1)]
    edges = []

    idx = 2
    for _ in range(m):
        u = int(data[idx])
        v = int(data[idx + 1])
        idx += 2
        adj[u].append(len(edges))
        edges.append([u, v, 1, 0])
        adj[v].append(len(edges))
        edges.append([v, u, 0, 0])

    source = 1
    sink = n
    total_flow = 0

    while True:
        parent_edge = [-1] * (n + 1)
        queue = deque([source])
        while queue:
            curr = queue.popleft()
            if curr == sink:
                break
            for edge_idx in adj[curr]:
                u, v, cap, flow = edges[edge_idx]
                if cap - flow > 0 and parent_edge[v] == -1 and v != source:
                    parent_edge[v] = edge_idx
                    queue.append(v)

        if parent_edge[sink] == -1:
            break

        curr = sink
        while curr != source:
            edge_idx = parent_edge[curr]
            edges[edge_idx][3] += 1
            edges[edge_idx ^ 1][3] -= 1
            curr = edges[edge_idx][0]

        total_flow += 1

    print(total_flow)

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

    for _ in range(total_flow):
        path = [source]
        curr = source
        while curr != sink:
            nxt = graph[curr].pop()
            path.append(nxt)
            curr = nxt
        print(len(path))
        print(*(path))

if __name__ == '__main__':
    solve()

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