Distinct Routes

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])

    # Edge arrays: edge i and i^1 are a forward/reverse pair
    to = []
    cap = []
    adj = [[] for _ in range(n + 1)]

    idx = 2
    for _ in range(m):
        a, b, c = int(data[idx]), int(data[idx + 1]), 1
        idx += 2
        adj[a].append(len(to)); to.append(b); cap.append(c)
        adj[b].append(len(to)); to.append(a); cap.append(0)

    s, t = 1, n
    flow = 0
    while True:
        # BFS for shortest augmenting path
        prev_edge = [-1] * (n + 1)
        visited = [False] * (n + 1)
        visited[s] = True
        q = deque([s])
        while q and not visited[t]:
            u = q.popleft()
            for e in adj[u]:
                v = to[e]
                if not visited[v] and cap[e] > 0:
                    visited[v] = True
                    prev_edge[v] = e
                    q.append(v)

        if not visited[t]:
            break

        # Find bottleneck along the path
        bottleneck = float('inf')
        v = t
        while v != s:
            e = prev_edge[v]
            bottleneck = min(bottleneck, cap[e])
            v = to[e ^ 1]

        # Augment
        v = t
        while v != s:
            e = prev_edge[v]
            cap[e] -= bottleneck
            cap[e ^ 1] += bottleneck
            v = to[e ^ 1]

        flow += bottleneck

    print(flow)

    used = [False] * len(to)
    out = []
    for _ in range(flow):
        path = [s]
        u = s
        while u != t:
            # print(used)
            for e in adj[u]:
                if e % 2 == 0 and cap[e] == 0 and not used[e]:
                    # print(e, u)
                    used[e] = True
                    u = to[e]
                    path.append(u)
                    # print(path)
                    break
        out.append(str(len(path)))
        out.append(' '.join(map(str, path)))
        # print(out)
    print('\n'.join(out))


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