Problem: There is a directed graph with N vertices and N edges. The vertices are numbered 1, 2, ..., N.  The graph has the following N edges: (p_1, 1), (p_2, 2), ..., (p_N, N), and the graph is weakly connected. Here, an edge from Vertex u to Vertex v is denoted by (u, v), and a weakly connected graph is a graph which would be connected if each edge was bidirectional.  We would like to assign a value to each of the vertices in this graph so that the following conditions are satisfied. Here, a_i is the value assigned to Vertex i.    * Each a_i is a non-negative integer.   * For each edge (i, j), a_i \neq a_j holds.   * For each i and each integer x(0 ≤ x < a_i), there exists a vertex j such that the edge (i, j) exists and x = a_j holds.  Determine whether there exists such an assignment.

Submission attempts (in order):
from collections import defaultdict
import heapq as hq


def helper(n):
    q = child_L[n]
    del child_L[n]

    hq.heapify(q)
    i = 0
    while q:
        t = hq.heappop(q)
        if i < t:
            break
        else:
            i += (i == t)

    j = i + 1
    while q:
        t = hq.heappop(q)
        if j < t:
            break
        else:
            j += (j == t)

    return (i, j)


if __name__ == '__main__':

    N = int(input())
    P = list(map(lambda x: int(x) - 1, input().split()))
    
    D = [0] * N
    for p in P:
        D[p] += 1
    # print(D)
    child_L = defaultdict(list)
    
    S = [p for p in range(N) if D[p] == 0]

    L = [None] * N

    while S:
        # print(child_L)
        n = S.pop()

        q = child_L[n]
        print(q)
        del child_L[n]

        
        hq.heapify(q)
        i = 0
        while q:
            t = hq.heappop(q)
            if i < t:
                break
            else:
                i += (i == t)

        L[n] = i
        print(L)
        m = P[n]
        print("m:" + str(m))
        child_L[m].append(i)
        D[m] -= 1
        if D[m] == 0:
            S.append(m)

    print(D)
    # cycle check
    try:
        start = D.index(1)
    except ValueError:
        print('POSSIBLE')
        exit()

    s1, s2 = helper(start)
    G = []
    n = P[start]
    while n != start:
        G.append(helper(n))
        n = P[n]

    

    
    # 1
    n = s1
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n != s1:
        print('POSSIBLE')
        exit()

    # 2
    n = s2
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n == s1:
        print('POSSIBLE')
        exit()

    print('IMPOSSIBLE')


from collections import defaultdict
import heapq as hq


def helper(n):
    q = child_L[n]
    del child_L[n]

    hq.heapify(q)
    i = 0
    while q:
        t = hq.heappop(q)
        if i < t:
            break
        else:
            i += (i == t)

    j = i + 1
    while q:
        t = hq.heappop(q)
        if j < t:
            break
        else:
            j += (j == t)

    return (i, j)


if __name__ == '__main__':

    N = int(input())
    P = list(map(lambda x: int(x) - 1, input().split()))
    
    D = [0] * N
    for p in P:
        D[p] += 1
    # print(D)
    child_L = defaultdict(list)
    
    S = [p for p in range(N) if D[p] == 0]

    L = [None] * N

    while S:
        # print(child_L)
        n = S.pop()

        q = child_L[n]
        # print(q)
        del child_L[n]

        
        hq.heapify(q)
        i = 0
        while q:
            t = hq.heappop(q)
            if i < t:
                break
            else:
                i += (i == t)

        L[n] = i
        # print(L)
        m = P[n]
        # print("m:" + str(m))
        child_L[m].append(i)
        D[m] -= 1
        if D[m] == 0:
            S.append(m)

    # print(D)
    # cycle check
    try:
        start = D.index(1)
    except ValueError:
        print('POSSIBLE')
        exit()

    s1, s2 = helper(start)
    G = []
    n = P[start]
    while n != start:
        G.append(helper(n))
        n = P[n]

    

    
    # 1
    n = s1
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n != s1:
        print('POSSIBLE')
        exit()

    # 2
    n = s2
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n == s1:
        print('POSSIBLE')
        exit()

    print('IMPOSSIBLE')


Verdicts: Runtime Error

Accepted