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: Wrong Answer

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

Submission status: Wrong Answer

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"))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
res=res[::-1]
for v in res:
    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

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
if not mex[dp[start]]:
    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
if not mex[dp[start]]:
    exit(print("POSSIBLE"))

print("IMPOSSIBLE")

Submission status: Wrong Answer

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)

assert len(Com[0]) > 1 ,''
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):
        for vf in Edge[vn]:
            if vc[vn] == vc[vf]:
                break
        else:
            continue
        break
    else:
        ans = True
        break
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Wrong Answer

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):
        assert vc[vn] is not None, 'Er'
        for vf in Edge[vn]:
            if vc[vn] == vc[vf]:
                break
        else:
            continue
        break
    else:
        ans = True
        break
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Wrong Answer

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):
        for vf in Edge[vn]:
            if vc[vn] == vc[vf]:
                break
        else:
            continue
        break
    else:
        ans = True
        break

print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N=int(input())
p=[i-1 for i in map(int,input().split())]
G=[[] for i in range(N)]
for i,a in enumerate(p):
  G[a].append(i)
visited=[False]*N
Circle_=[0]
while not visited[Circle_[-1]]:
  visited[Circle_[-1]]=True
  Circle_.append(p[Circle_[-1]])
Circle=[Circle_[-1]]
inCircle=[False]*N
for i in Circle_[:len(Circle_)-1][::-1]:
  inCircle[i]=True
  Circle.append(i)
  if i==Circle_[-1]:
    break
#print(Circle)
#print(G)
num=[[]]*N
def dfs(x):
  List=[False]*N
  for a in G[x]:
    if inCircle[a]:
      continue
    List[dfs(a)]=True
  if inCircle[x]:
    res=[]
    for i in range(N+1):
      if not List[i]:
        if not res:
          res.append(i)
        else:
          res.append(i)
          num[x]=res
          return res
  else:
    for i in range(N+1):
      if not List[i]:
        num[x]=[i]
        return i
for i in Circle:
  dfs(i)
#print(inCircle)
#print(num)
s,t=num[Circle[-1]][0],num[Circle[-1]][0]
for i in Circle[:len(Circle)-1][::-1]:
  if num[i][0]==t:
    t=num[i][1]
  else:
    t=num[i][0]
  #print(i,t)
if t==s:
  print("POSSIBLE")
  exit()
s,t=num[Circle[-1]][1],num[Circle[-1]][1]
for i in Circle[:len(Circle)-1][::-1]:
  if num[i][0]==t:
    t=num[i][1]
  else:
    t=num[i][0]
 # print(i,t)
if t==s:
  print("POSSIBLE")
else:
  print("INPOSSIBLE")

Submission status: Wrong Answer

Solution code:
print "IMPOSSIBLE"

Submission status: Wrong Answer

Solution code:
# F
N = int(input())
p_list = list(map(int, input().split()))

# usagi to kame
# start from 1
usagi = 1
kame  = 1

def back(i):
    return p_list[i - 1]

usagi = back(back(usagi))
kame = back(kame)

while usagi != kame:
    usagi = back(back(usagi))
    kame = back(kame)

# begin loop
# length of loop
L = 1
usagi = back(back(usagi))
kame = back(kame)

while usagi != kame:
    usagi = back(back(usagi))
    kame = back(kame)
    L += 1
    
if L % 2 == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N=int(input())
p=[i-1 for i in map(int,input().split())]
G=[[] for i in range(N)]
for i,a in enumerate(p):
  G[a].append(i)
visited=[False]*N
Circle_=[0]
while not visited[Circle_[-1]]:
  visited[Circle_[-1]]=True
  Circle_.append(p[Circle_[-1]])
Circle=[Circle_[-1]]
inCircle=[False]*N
for i in Circle_[:len(Circle_)-1][::-1]:
  inCircle[i]=True
  Circle.append(i)
  if i==Circle_[-1]:
    break
#print(Circle)
#print(G)
num=[[]]*N
def dfs(x):
  List=[False]*N
  for a in G[x]:
    if inCircle[a]:
      continue
    List[dfs(a)]=True
  if inCircle[x]:
    res=[]
    for i in range(N+1):
      if not List[i]:
        if not res:
          res.append(i)
        else:
          res.append(i)
          num[x]=res
          return res
  else:
    for i in range(N+1):
      if not List[i]:
        num[x]=[i]
        return i
for i in Circle:
  dfs(i)
#print(inCircle)
#print(num)
s,t=num[Circle[-1]][0],num[Circle[-1]][0]
for i in Circle[:len(Circle)-1][::-1]:
  if num[i][0]==t:
    t=num[i][1]
  else:
    t=num[i][0]
  #print(i,t)
if t==s:
  print("POSSIBLE")
  exit()
s,t=num[Circle[-1]][1],num[Circle[-1]][1]
for i in Circle[:len(Circle)-1][::-1]:
  if num[i][0]==t:
    t=num[i][1]
  else:
    t=num[i][0]
 # print(i,t)
if t==s:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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)
grundy = [-1] * (N + 1)
used = [False] * (N + 2)

def func(pos, start):
    if used[pos]:
        if pos == start:
            return INF
        else:
            return grundy[pos]
    used[pos] = True
    ret = [func(to, start) for to in E[pos]]
    if INF in ret:
        grundy[pos] = INF
        return INF
    for num in ret:
        flag[num] = False
    i = 0
    while True:
        if flag[i]:
            grundy[pos] = i
            val = i
            break
        i += 1
    for num in ret:
        flag[num] = True
    return val

grundy_ = []

def func2(pos):
    if grundy_[pos] != INF:
        return grundy_[pos]
    ret = [func2(to) for to in E[pos]]
    for num in ret:
        flag[num] = False
    i = 0
    while True:
        if flag[i]:
            grundy_[pos] = i
            val = i
            break
        i += 1
    for num in ret:
        flag[num] = True
    return val

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, i)
        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)
        #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)
grundy = [-1] * (N + 1)

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

grundy_ = []

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

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i)
        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)
        #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)
R = range(N + 1)

flag = [True] * (N + 2)
grundy = [-1] * (N + 1)

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

grundy_ = []

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

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i)
        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)
        #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)
R = range(N + 1)

flag = [True] * (N + 2)
grundy = [-1] * (N + 1)

def func(pos, pre, start):
    if grundy[pos] != -1:
        return grundy[pos]
    if pos == start and pre != -1:
        return INF
    ret = [func(to, pos, start) for to in E[pos]]
    if INF in ret:
        grundy[pos] = INF
        return INF
    for num in ret:
        flag[num] = False
    for i in R:
        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 R:
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i)
        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)
grundy = [-1] * (N + 1)

def func(pos, pre, start):
    if grundy[pos] != -1:
        return grundy[pos]
    if pos == start and pre != -1:
        return INF
    ret = [func(to, pos, start) 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

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i)
        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