Distinct Routes

from collections import deque, defaultdict

def bfs(n, adj):
    parent = [-1] * (n + 1)
    visited = [False] * (n + 1)
    visited[1] = True
    q = deque([1])

    while q:
        u = q.popleft()

        if u == n:
            path = []
            while u != -1:
                path.append(u)
                u = parent[u]
            path.reverse()
            return path

        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                q.append(v)

    return None

def remove_path(path, adj):
    for i in range(len(path) - 1):
        u, v = path[i], path[i + 1]
        adj[u].remove(v)

def main():
    n, m = map(int, input().split())
    adj = defaultdict(list)
    
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a].append(b)
    
    routes = []
    while True:
        path = bfs(n, adj)
        if not path:
            break
        routes.append(path)
        remove_path(path, adj)
    
    print(len(routes))
    for route in routes:
        print(len(route))
        print(' '.join(map(str, route)))

if __name__ == "__main__":
    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: WRONG ANSWER

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER