Distinct Routes

n, m = [int(x) for x in input().split()]
graph = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    graph[a-1][b-1] = 1

def bfs(start, end):
    visited = [False]*n
    queue = []
    queue.append(start)
    visited[start] = True

    while queue:
        node = queue.pop(0)
        for i, nei in enumerate(graph[node]):
            if not visited[i] and nei > 0:
                queue.append(i)
                visited[i] = True
                parent[i] = node
    
    return visited[end]

parent = [-1]*n
max = 0
all_paths = []
while bfs(0, n-1):
    path = []
    node = n-1
    while node != -1:
        path.append(node+1)
        node = parent[node]
    path.reverse()
    all_paths.append(path)
    max += 1

    for i in range(len(path)-1):
        u = path[i]-1
        v = path[i+1]-1
        graph[u][v] -= 1

print(max)
if max > 0:
    for path in all_paths:
        print(len(path))
        print(*path)

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: WRONG ANSWER

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER