import sys

# Increase recursion depth for large puzzles
sys.setrecursionlimit(2000)

def solve(cells):
    n = len(cells)
    # We map values 1...n to indices 0...n-1
    # Graph: Left side (cells 0 to n-1), Right side (values 0 to n-1)
    
    # 1. Find an initial Perfect Matching
    match_val_to_cell = [-1] * n
    match_cell_to_val = [-1] * n

    def dfs_matching(u, visited):
        for v_idx in cells[u]:
            v = v_idx - 1 # 0-indexed
            if not visited[v]:
                visited[v] = True
                if match_val_to_cell[v] < 0 or dfs_matching(match_val_to_cell[v], visited):
                    match_val_to_cell[v] = u
                    match_cell_to_val[u] = v
                    return True
        return False

    for i in range(n):
        dfs_matching(i, [False] * n)
    print(match_val_to_cell)
    print(match_cell_to_val)
    # 2. Build Directed Graph for SCC
    # Cell nodes: 0 to n-1 | Value nodes: n to 2n-1
    adj = [[] for _ in range(2 * n)]
    for u, candidates in enumerate(cells):
        for v_idx in candidates:
            v = v_idx - 1
            if match_cell_to_val[u] == v:
                # Edge in matching: Value -> Cell
                adj[v + n].append(u)
            else:
                # Edge NOT in matching: Cell -> Value
                adj[u].append(v + n)
    print(adj)
    # 3. Find SCCs using Tarjan's
    discovery_time = [-1] * (2 * n)
    low_link = [-1] * (2 * n)
    stack = []
    on_stack = [False] * (2 * n)
    scc_id = [-1] * (2 * n)
    timer = 0
    scc_count = 0

    def find_scc(u):
        nonlocal timer, scc_count
        discovery_time[u] = low_link[u] = timer
        timer += 1
        stack.append(u)
        on_stack[u] = True

        for v in adj[u]:
            if discovery_time[v] == -1:
                find_scc(v)
                low_link[u] = min(low_link[u], low_link[v])
            elif on_stack[v]:
                low_link[u] = min(low_link[u], discovery_time[v])

        if low_link[u] == discovery_time[u]:
            while True:
                node = stack.pop()
                on_stack[node] = False
                scc_id[node] = scc_count
                if node == u: break
            scc_count += 1

    for i in range(2 * n):
        if discovery_time[i] == -1:
            find_scc(i)

    # 4. Filter candidates
    ans = [set() for _ in range(n)]
    for u in range(n):
        for v_idx in cells[u]:
            v = v_idx - 1
            # Condition: Edge is in perfect matching OR part of a cycle (same SCC)
            if match_cell_to_val[u] == v or scc_id[u] == scc_id[v + n]:
                ans[u].add(v_idx)
    
    return ans

cells = [{1,2}, {1,2}, {1,2,3}]
out = solve([{1, 2}, {1, 2}, {3}]) 
print(out)