Distinct Routes

import sys
from collections import deque

sys.setrecursionlimit(2000)

class Edge:
    def __init__(self, to, cap, rev):
        self.to = to
        self.cap = cap
        self.flow = 0
        self.rev = rev

def add_edge(adj, u, v, cap):
    a = Edge(v, cap, len(adj[v]))
    b = Edge(u, 0, len(adj[u]))
    adj[u].append(a)
    adj[v].append(b)

def bfs(adj, s, t, parent):
    visited = [False] * len(adj)
    queue = deque([s])
    visited[s] = True
    
    while queue:
        u = queue.popleft()
        if u == t:
            return True
        for i, edge in enumerate(adj[u]):
            if not visited[edge.to] and edge.cap - edge.flow > 0:
                visited[edge.to] = True
                parent[edge.to] = (u, i)
                queue.append(edge.to)
                
    return False

def max_flow(adj, s, t):
    total_flow = 0
    parent = [None] * len(adj)
    
    while bfs(adj, s, t, parent):
        push = float('inf')
        curr = t
        while curr != s:
            p_node, p_edge_idx = parent[curr]
            edge = adj[p_node][p_edge_idx]
            push = min(push, edge.cap - edge.flow)
            curr = p_node
            
        curr = t
        while curr != s:
            p_node, p_edge_idx = parent[curr]
            edge = adj[p_node][p_edge_idx]
            edge.flow += push
            adj[edge.to][edge.rev].flow -= push
            curr = p_node
            
        total_flow += push
        
    return total_flow

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    n = int(input_data[0])
    m = int(input_data[1])
    
    adj = [[] for _ in range(n + 1)]
    
    idx = 2
    for _ in range(m):
        u = int(input_data[idx])
        v = int(input_data[idx + 1])
        add_edge(adj, u, v, 1)
        idx += 2
        
    s, t = 1, n
    k = max_flow(adj, s, t)
    
    print(k)
    
    for _ in range(k):
        path = [1]
        curr = 1
        
        while curr != t:
            for edge in adj[curr]:
                if edge.flow > 0:
                    edge.flow -= 1  
                    curr = edge.to
                    path.append(curr)
                    break
                    
        print(len(path))
        print(*(path))

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