Problem:


Score : 800 points

Problem Statement

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.

Constraints

2 ≤ N ≤ 200 000

1 ≤ p_i ≤ N

p_i \neq i

The graph is weakly connected.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_N

Output

If the assignment is possible, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

4
2 3 4 1

Sample Output 1

POSSIBLE

The assignment is possible: {a_i} = {0, 1, 0, 1} or {a_i} = {1, 0, 1, 0}.

Sample Input 2

3
2 3 1

Sample Output 2

IMPOSSIBLE

Sample Input 3

4
2 3 1 1

Sample Output 3

POSSIBLE

The assignment is possible: {a_i} = {2, 0, 1, 0}.

Sample Input 4

6
4 5 6 5 6 4

Sample Output 4

IMPOSSIBLE



Sample input:
4
2 3 4 1


Sample output:
POSSIBLE

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
p = map(int, raw_input().split())
E = [[] for i in range(N + 1)]
for i in range(N):
    E[p[i]].append(i + 1)

flag = [True] * (N + 2)

def func(pos, pre, start, grundy):
    if grundy[pos] != -1:
        return grundy[pos]
    if pos == start and pre != -1:
        return INF
    ret = [func(to, pos, start, grundy) for to in E[pos]]
    if INF in ret:
        grundy[pos] = INF
        return INF
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

def func2(pos, grundy):
    if grundy[pos] != -1 and grundy[pos] != INF:
        return grundy[pos]
    ret = [func2(to, grundy) for to in E[pos]]
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

grundy = [-1] * (N + 1)

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i, grundy)
        if ret == INF:
            pos = i
            break

ff = [True] * (N + 2)
nex = 0
for to in E[pos]:
    if grundy[to] == INF:
        nex = to
    else:
        ff[grundy[to]] = False
cnt = 0
for i in range(N + 2):
    if ff[i]:
        grundy_ = list(grundy)
        grundy_[pos] = i
        func2(nex, grundy_)
        #print grundy_
        if cnt == 0:
            pre = grundy_[pos]
            if grundy_[pos] != grundy_[nex]:
                print "POSSIBLE"
                exit()
        if cnt == 1:
            if grundy_[nex] == pre:
                print "POSSIBLE"
            else:
                print "IMPOSSIBLE"
            exit()
        cnt += 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
p = map(int, raw_input().split())
E = [[] for i in range(N + 1)]
for i in range(N):
    E[p[i]].append(i + 1)

flag = [True] * (N + 2)

def func(pos, pre, start, grundy):
    if grundy[pos] != -1:
        return grundy[pos]
    if pos == start and pre != -1:
        return INF
    ret = [func(to, pos, start, grundy) for to in E[pos]]
    if INF in ret:
        grundy[pos] = INF
        return INF
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

def func2(pos, grundy):
    if grundy[pos] != -1 and grundy[pos] != INF:
        return grundy[pos]
    ret = [func2(to, grundy) for to in E[pos]]
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

grundy = [-1] * (N + 1)

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i, grundy)
        if ret == INF:
            pos = i
            break
ret = []
nex = 0
for to in E[pos]:
    ret += [grundy[to]]
    if grundy[to] == INF:
        nex = to
ret = set(ret)
cnt = 0
for i in range(N + 2):
    if not i in ret:
        grundy_ = list(grundy)
        grundy_[pos] = i
        func2(nex, grundy_)
        #print grundy_
        if cnt == 0:
            pre = grundy_[pos]
            if grundy_[pos] != grundy_[nex]:
                print "POSSIBLE"
                exit()
        if cnt == 1:
            if grundy_[nex] == pre:
                print "POSSIBLE"
            else:
                print "IMPOSSIBLE"
            exit()
        cnt += 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
p = map(int, raw_input().split())
E = [[] for i in range(N + 1)]
for i in range(N):
    E[p[i]].append(i + 1)

flag = [True] * (N + 2)

def func(pos, pre, start, grundy):
    if grundy[pos] != -1:
        return grundy[pos]
    if pos == start and pre != -1:
        return INF
    ret = []
    ex = False
    for to in E[pos]:
        S = func(to, pos, start, grundy)
        if S == INF:
            ex = True
        ret.append(S)
    if ex:
        grundy[pos] = INF
        return INF
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

def func2(pos, grundy):
    if grundy[pos] != -1 and grundy[pos] != INF:
        return grundy[pos]
    ret = []
    for to in E[pos]:
        S = func2(to, grundy)
        ret.append(S)
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

grundy = [-1] * (N + 1)

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i, grundy)
        if ret == INF:
            pos = i
            break
ret = []
nex = 0
for to in E[pos]:
    ret += [grundy[to]]
    if grundy[to] == INF:
        nex = to
ret = set(ret)
cnt = 0
for i in range(N + 2):
    if not i in ret:
        grundy_ = list(grundy)
        grundy_[pos] = i
        func2(nex, grundy_)
        #print grundy_
        if cnt == 0:
            pre = grundy_[pos]
            if grundy_[pos] != grundy_[nex]:
                print "POSSIBLE"
                exit()
        if cnt == 1:
            if grundy_[nex] == pre:
                print "POSSIBLE"
            else:
                print "IMPOSSIBLE"
            exit()
        cnt += 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
p = map(int, raw_input().split())
E = [[] for i in range(N + 1)]
for i in range(N):
    E[p[i]].append(i + 1)

def func(pos, pre, start, grundy):
    if grundy[pos] != -1:
        return grundy[pos]
    if pos == start and pre != -1:
        return INF
    ret = []
    for to in E[pos]:
        ret += [func(to, pos, start, grundy)]
    ret = set(ret)
    if INF in ret:
        grundy[pos] = INF
        return INF
    for i in range(N + 1):
        if not i in ret:
            grundy[pos] = i
            return i

def func2(pos, grundy):
    if grundy[pos] != -1 and grundy[pos] != INF:
        return grundy[pos]
    ret = []
    for to in E[pos]:
        ret += [func2(to, grundy)]
    ret = set(ret)
    for i in range(N + 1):
        if not i in ret:
            grundy[pos] = i
            return i

grundy = [-1] * (N + 1)

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i, grundy)
        if ret == INF:
            pos = i
            break
ret = []
nex = 0
for to in E[pos]:
    ret += [grundy[to]]
    if grundy[to] == INF:
        nex = to
ret = set(ret)
cnt = 0
#print pos, nex
for i in range(N + 2):
    if not i in ret:
        grundy_ = list(grundy)
        grundy_[pos] = i
        func2(nex, grundy_)
        #print grundy_
        if cnt == 0:
            pre = grundy_[pos]
            if grundy_[pos] != grundy_[nex]:
                print "POSSIBLE"
                exit()
        if cnt == 1:
            if grundy_[nex] == pre:
                print "POSSIBLE"
            else:
                print "IMPOSSIBLE"
            exit()
        cnt += 1

Submission status: Time Limit Exceeded

Solution code:
# 結局は木+1辺
from collections import defaultdict
from itertools import count

N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))
D = [0]*N
for p in P:
  D[p] += 1

rE = defaultdict(list)
for i,p in enumerate(P):
  rE[p] += [i]

S = [p for p in range(N) if D[p] == 0]
L = [None]*N

while S:
  n = S.pop()
  prev = set(L[a] for a in rE[n])
  if prev:
    for i in count():
      if i not in prev:
        L[n] = i
  else:
    L[n] = 0
  
  m = P[n]
  D[m] -= 1
  if D[m] == 0:
    S.append(m)

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

def helper(n):
  s = set(L[a] for a in rE[n] if L[a] is not None)
  rlt = []
  for i in count():
    if i not in s:
      rlt.append(i)
      if len(rlt) >= 2:
        return rlt

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


del N,P,D,rE,S,L


# 可能な初期値をそれぞれシミュレート
# 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')

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    print("POSSIBLE")
    exit()

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for v in res:
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break

#m0
dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m0:
    print("POSSIBLE")
    exit()

for v in cycle:
    dp[v]=-1

#m1
dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[start])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m1:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
p = list(map(int, input().split()))
c = [[] for _ in range(n)]
is_leaf = [True for _ in range(n)]
for i in range(n):
	p[i] -= 1
	c[p[i]].append(i)
	is_leaf[p[i]] = False

if sum(is_leaf) == 0:
	if n%2 == 0:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
	sys.exit()

for i in range(n):
	if is_leaf[i]:
		cur = i
		break

visited_set = {cur}
visited_list = [cur]
while p[cur] not in visited_set:
	visited_list.append(p[cur])
	visited_set.add(p[cur])
	cur = p[cur]

root = p[cur]

grundy = [-1 for _ in range(n)]
g_set = [set() for _ in range(n)]

def dfs(x):
	res = 0
	for v in c[x]:
		dfs(v)
		g_set[x].add(grundy[v])
	while res in g_set[x]:
		res += 1
	grundy[x] = res
	return res

loop = [False for _ in range(n)]
loop[root] = True
ind = len(visited_list)-1
while visited_list[ind] != root:
	loop[visited_list[ind]] = True
	ind -= 1
#print(loop)

for i in range(n):
	if loop[i]:
		for x in c[i]:
			if not loop[x]:
				dfs(x)
				g_set[i].add(grundy[x])

cand = []
num = 0
while num in g_set[root]:
	num += 1
cand.append(num)
num += 1
while num in g_set[root]:
	num += 1
cand.append(num)

for x in cand:
	cur = root
	grundy[root] = x
	while True:
		num = 0
		while num in g_set[p[cur]] or num == grundy[cur]:
			num += 1
		grundy[p[cur]] = num
		if p[cur] == root:
			break
		cur = p[cur]
	if grundy[root] == x:
		#print(grundy)
		print("POSSIBLE")
		sys.exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from itertools import chain
readline = sys.stdin.readline

#非再帰
def scc(Edge):
    N = len(Edge)
    Edgeinv = [[] for _ in range(N)]
    for vn in range(N):
        for vf in Edge[vn]:
            Edgeinv[vf].append(vn)
    
    used = [False]*N
    dim = [len(Edge[i]) for i in range(N)]
    order = []
    for st in range(N):
        if not used[st]:
            stack = [st, 0]
            while stack:
                vn, i = stack[-2], stack[-1]   
                if not i and used[vn]:
                    stack.pop()
                    stack.pop()
                else:
                    used[vn] = True
                    if i < dim[vn]:
                        stack[-1] += 1
                        stack.append(Edge[vn][i])
                        stack.append(0)
                    else:
                        stack.pop()
                        order.append(stack.pop())
    res = [None]*N
    used = [False]*N
    cnt = -1
    for st in order[::-1]:
        if not used[st]:
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                vn = stack.pop()
                for vf in Edgeinv[vn]:
                    if not used[vf]:
                        used[vf] = True
                        res[vf] = cnt
                        stack.append(vf)
    M = cnt+1
    components = [[] for _ in range(M)]
    for i in range(N):
        components[res[i]].append(i)
    tEdge = [[] for _ in range(M)]
    teset = set()
    for vn in range(N):
        tn = res[vn]
        for vf in Edge[vn]:
            tf = res[vf]
            if tn != tf and tn*M + tf not in teset:
                teset.add(tn*M + tf)
                tEdge[tn].append(tf)
    return res, components, tEdge

N = int(readline())
P = list(map(lambda x: int(x)-1, readline().split()))

Edge = [[] for _ in range(N)]
for i in range(N):
    Edge[P[i]].append(i)

R, Com, _ = scc(Edge)

Lord = list(chain(*Com[::-1]))
val = [None]*N
for vn in Lord:
    if not R[vn]:
        break
    lvn = len(Edge[vn]) + 1
    res = [0]*lvn
    for vf in Edge[vn]:
        if val[vf] < lvn:
            res[val[vf]] += 1
    
    for k in range(lvn):
        if not res[k]:
            val[vn] = k
            break

st = Lord[-1]
lst = len(Edge[st]) + 2
res = [0]*lst
for vf in Edge[st]:
    if val[vf] is None:
        continue
    if val[vf] < lst:
        res[val[vf]] += 1
mc = []
for k in range(lst):
    if not res[k]:
        mc.append(k)

vn = st
Ls = []
while vn is not None:
    for vf in Edge[vn]:
        if R[vf]:
            continue
        if vf == st:
            vn = None
        else:
            Ls.append(vf)
            vn = vf

Ls.reverse()

ans = False
for idx in range(2):
    vc = val[:]
    vc[st] = mc[idx]
    for vn in Ls:
        lvn = len(Edge[vn])+1
        res = [0]*lvn
        for vf in Edge[vn]:
            if vc[vf] < lvn:
                res[vc[vf]] += 1
        
        for k in range(lvn):
            if not res[k]:
                vc[vn] = k
                break
    
    for vn in range(N):
        res = [False]*vc[vn]
        for vf in Edge[vn]:
            if vc[vn] == vc[vf]:
                break
            if vc[vf] < vc[vn]:
                res[vc[vf]] = True
        else:
            if not all(res):
                break
            continue
        break
    else:
        ans = True
    if ans:
        break
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・pseudo-tree graph
・in_deg = 1が保証されているので、向きの揃ったcycleがある
・1箇所の2択を決めれば全部決まる
"""

N = int(readline())
parent = [0] + list(map(int,read().split()))

child = [[] for _ in range(N+1)]
for i,x in enumerate(parent):
    child[x].append(i)

out_deg = [len(x) for x in child]

out_deg

G = [-1] * (N+1)

# とりあえず唯一のサイクル以外を処理：out_deg=0の頂点を捨てていく

stack = [i for i,x in enumerate(out_deg) if not x]
while stack:
    x = stack.pop()
    se = set(G[c] for c in child[x])
    g = 0
    while g in se:
        g += 1
    G[x] = g
    p = parent[x]
    out_deg[p] -= 1
    if not out_deg[p]:
        stack.append(p)

"""
・grundy数の候補は2種。
・片方決め打って計算。2周grundy数を計算してstableになっていればよい。
"""

for i,x in enumerate(out_deg[1:],1):
    if x==1:
        root = i
        break

cycle_len = sum(out_deg[1:])

is_stable = False
x = root
for _ in range(cycle_len*2+10):
    se = set(G[c] for c in child[x])
    g = 0
    while g in se:
        g += 1
    if g == G[x]:
        is_stable = True
        break
    G[x] = g
    x = parent[x]

answer = 'POSSIBLE' if is_stable else 'IMPOSSIBLE'
print(answer)

Submission status: Accepted

Solution code:
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:出している辺の本数
    D = [0] * N
    for p in P:
        D[p] += 1
    # print(D)
    child_L = defaultdict(list)
    # S:辺を出してないものリスト
    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]

        # listのqをヒープキューに変換
        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]

    # del N, P, D, child_L, S, L

    # 可能な初期値をそれぞれシミュレート
    # 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')

Submission status: Accepted

Solution code:
# 結局は木+1辺
from collections import defaultdict
import heapq as hq

N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))
D = [0]*N
for p in P:
  D[p] += 1

child_L = defaultdict(list)

S = [p for p in range(N) if D[p] == 0]
L = [None]*N

while S:
  n = S.pop()

  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)
  
  L[n] = i
  m = P[n]
  child_L[m].append(i)
  D[m] -= 1
  if D[m] == 0:
    S.append(m)

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

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)


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


del N,P,D,child_L,S,L


# 可能な初期値をそれぞれシミュレート
# 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')

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    print("POSSIBLE")
    exit()

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for v in res:
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break

#m0
dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m0:
    print("POSSIBLE")
    exit()

for v in cycle:
    dp[v]=-1

#m1
dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    print("POSSIBLE")
    exit()

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for v in res:
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break

#m0
dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m0:
    print("POSSIBLE")
    exit()

for v in cycle:
    dp[v]=-1

#m1
dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m1:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    exit(print("POSSIBLE"))

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for v in res:
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break

#m0
dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m0:
    exit(print("POSSIBLE"))

for v in cycle:
    dp[v]=-1

#m1
dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if check==m1:
    exit(print("POSSIBLE"))

print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    exit(print("POSSIBLE"))

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for v in res:
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break

#m0
dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if i==m0:
    exit(print("POSSIBLE"))

for v in cycle:
    dp[v]=-1

#m1
dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
check=-1
for i in range(len(mex)):
    if not mex[i]:
        check=i
        break
if i==m1:
    exit(print("POSSIBLE"))

print("IMPOSSIBLE")