Distinct Routes

from collections import deque

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

cap = [[0] * (n + 1) for _ in range(n + 1)]
flow = [[0] * (n + 1) for _ in range(n + 1)]
graph = [[] for _ in range(n + 1)]

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

days = 0
while True:
    parent = [0] * (n + 1)
    parent[1] = -1
    queue = deque([1])
    while queue and parent[n] == 0:
        u = queue.popleft()
        for v in graph[u]:
            if parent[v] == 0 and cap[u][v] - flow[u][v] > 0:
                parent[v] = u
                queue.append(v)

    if parent[n] == 0:
        break

    v = n
    while v != 1:
        u = parent[v]
        flow[u][v] += 1
        flow[v][u] -= 1
        v = u
    days += 1

print(days)
for _ in range(days):
    route = [1]
    u = 1
    while u != n:
        for v in graph[u]:
            if flow[u][v] > 0:
                flow[u][v] -= 1
                u = v
                break
        route.append(u)
    print(len(route))
    print(*route)

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