Problem:


Score : 800 points

Problem Statement

Niwango has N cards, numbered 1,2,\ldots,N.
He will now arrange these cards in a row.

Niwango wants to know if there is a way to arrange the cards while satisfying all the N conditions below.
To help him, determine whether such a way exists. If the answer is yes, also find the lexicographically smallest such arrangement.

To the immediate right of Card 1 (if any) is NOT Card a_1.

To the immediate right of Card 2 (if any) is NOT Card a_2.

\vdots

To the immediate right of Card N (if any) is NOT Card a_N.

Constraints

2 \leq N \leq 10^{5}

1 \leq a_i \leq N

a_i \neq i

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

If no arrangements satisfy the conditions, print -1. If such arrangements exist, print the lexicographically smallest such arrangement, in the following format:

b_1 b_2 \ldots b_N

Here, b_i represents the i-th card from the left.

Sample Input 1

4
2 3 4 1

Sample Output 1

1 3 2 4

The arrangement (1,2,3,4) is lexicographically smaller than (1,3,2,4), but is invalid, since it violates the condition "to the immediate right of Card 1 is not Card 2."

Sample Input 2

2
2 1

Sample Output 2

-1

If no arrangements satisfy the conditions, print -1.

Sample Input 3

13
2 3 4 5 6 7 8 9 10 11 12 13 12

Sample Output 3

1 3 2 4 6 5 7 9 8 10 12 11 13



Sample input:
4
2 3 4 1


Sample output:
1 3 2 4

Submission status: Runtime Error

Solution code:
import heapq
from itertools import permutations
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in range(n):
    a = A[i]
    if i+1 != a:
      ukeire[a-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while len(can)>3:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
        s = heapq.heappop(can)
        L.append(s)
        heapq.heappush(can, t)
    else:
      L.append(t)
  for i1, i2, i3 in permutations(sorted(can)):
    if A[L[-1]-1] != i1 and A[i1-1] != i2 and A[i2-1] != i3:
      print(*(L+[i1, i2, i3]))
      break

Submission status: Runtime Error

Solution code:
import heapq
from itertools import permutations
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in range(n):
    a = A[i]
    if i+1 != a:
      ukeire[a-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while len(can)>3:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
        s = heapq.heappop(can)
        L.append(s)
        heapq.heappush(can, t)
    else:
      L.append(t)
  for i1, i2, i3 in permutations(can):
    if A[L[-1]-1] != i1 and A[i1-1] != i2 and A[i2-1] != i3:
      print(*(L+[i1, i2, i3]))
      break

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(map(int, input().split()))
ans = []
H = []
for i in range(2,N+1):
    H.append(i)
ans.append(1)
i=0
j=0
if(N==2):
    if(X[0]==2 and X[1]==1):
        ans=-1
else:
    #print(len(H))
    while(len(H)>=2):
        if (H[i]!=X[ans[j]-1]):
            j+=1
            ans.append(H[i])
            H.remove(H[i])
            i=0
            #print(ans)
        else:
            i+=1
    #print(len(ans))
    #print(H[0])
    #print(ans[N-2])
    #print(X[ans[N-2]-1])
    if (H[0]==X[ans[N-2]-1]):
        #print("A")
        for l in range(1,N-1):
            if(X[ans[N-2-l]-1]!=H[0]and X[H[0]-1]!=ans[N-1-l]):
                ans.insert(N-1-l,H[0])
                break
    else:
        ans.append(H[0])
ans=[str(a) for a in ans]
ans=" ".join(ans)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
from heapq import heapify, heappush, heappop
import sys

N = int(input())
As = [A-1 for A in map(int, input().split())]

if As == [1, 0]:
    print(-1)
    sys.exit()

cnt = Counter(As)

anss = []
useds = [False] * N
PQ = list(range(N))
heapify(PQ)
for i in range(N):
    ans = -1
    if len(cnt) == 2:
        for A, num in cnt.items():
            if num == N-1-i:
                ans = min(ans, A)
    if ans == -1:
        ans = heappop(PQ)
        B = -1
        while True:
            if useds[ans]:
                ans = heappop(PQ)
            else:
                if len(anss) > 0 and As[anss[-1]] == ans:
                    B = ans
                    ans = heappop(PQ)
                else:
                    break
        if B != -1:
            heappush(PQ, B)

    anss.append(ans)
    useds[ans] = True
    cnt[As[ans]] -= 1
    if cnt[As[ans]] == 0:
        del cnt[As[ans]]

print(' '.join(map(lambda x: str(x+1), anss)))

Submission status: Runtime Error

Solution code:
import sys

def chk(s,p,q,r):
    if s!=p and a[p-1]!=q and a[q-1]!=r: return 1
    else: return 0

n=int(input())
a=list(map(int,input().split()))

if n==2 and a==[2,1]: print(-1),sys.exit()

x=[i+2 for i in range(n-1)]
ans=[1]

for i in range(n-1):
    tmp=ans[-1]-1
    if a[tmp]!=x[0]:
        ans.append(x.pop(0))
    elif i==n-2:
        ans.append(x.pop(0))
        [p,q,r]=[ans[n-3:n]].sort()
        s=a[ans[n-4]-1]
        if chk(s,p,q,r)==1: xx=[p,q,r]
        elif chk(s,p,r,q)==1: xx=[p,r,q]
        elif chk(s,q,p,r)==1: xx=[q,p,r]
        elif chk(s,q,r,p)==1: xx=[q,r,p]
        elif chk(s,r,p,q)==1: xx=[r,p,q]
        elif chk(s,r,q,p)==1: xx=[r,q,p]
        ans[n-3:n]=[xx]

    else: ans.append(x.pop(1))




for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
import sys

def chk(p,q,r):
    if a[ans[n-4]-1]!=p and a[p-1]!=q and a[q-1]!=r: return 1
    else: return 0

n=int(input())
a=list(map(int,input().split()))

if n==2 and a==[2,1]: print(-1),sys.exit()

x=[i+2 for i in range(n-1)]
ans=[1]

for i in range(n-1):
    tmp=ans[-1]-1
    if a[tmp]!=x[0]:
        ans.append(x.pop(0))
    elif i==n-2:
        ans.append(x.pop(0))
        [p,q,r]=[ans[n-3],ans[n-2],ans[n-1]].sort()
        if chk(p,q,r)==1: xx=[p,q,r]
        elif chk(p,r,q)==1: xx=[p,r,q]
        elif chk(q,p,r)==1: xx=[q,p,r]
        elif chk(q,r,p)==1: xx=[q,r,p]
        elif chk(r,p,q)==1: xx=[r,p,q]
        elif chk(r,q,p)==1: xx=[r,q,p]
        ans[n-3:n]=[xx]

    else: ans.append(x.pop(1))




for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
A=list(map(int,input().split()))
l=deque([i for i in range(2,n+1)])
ans=[1]
for i in range(n-1):
    a=l.popleft()
    if a==A[ans[i]-1]:
        if l:
            b=l.popleft()
            ans.append(b)
            l.appendleft(a)
        else:
            c=A[a-1]
            for j in range(n-2):
                if c!=ans[-j-1] and A[ans[-j-2]-1]!=a:
                    ans=ans[:-j-1]+[a]+[-j-1:]
                    print(ans)
                    exit()
            if c!=ans[0]:
                ans=[a]+ans
                print(ans)
            else:
                print(-1)            
    else:
        ans.append(a)
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

for i in range(n):
    A[i] -= 1

ANS = [0]
B = [0] * n
# B[0] = 1

if n==2 and A==[2,1]:
    print(-1)
elif n==2:
    print("1 2")
else:

    a = 1
    b = 2
    while len(ANS) < n-3:
        if A[ANS[-1]] != a:
            ANS.append(a)

            a = b
        elif A[ANS[-1]] != b:
            ANS.append(b)
        b += 1
    # print([i+1 for i in ANS])

    for i in range(len(ANS)):
        B[ANS[i]] += 1
    N = []
    for i in range(len(B)):
        if B[i] == 0:
            N.append(i)
    N.sort()

    M = [[N[0],N[1],N[2]],[N[0],N[2],N[1]],[N[1],N[0],N[2]],\
    [N[1],N[2],N[0]],[N[2],N[0],N[1]],[N[2],N[1],N[0]]]

    for i in range(6):
        if A[ANS[-1]] != M[i][0] and A[M[i][0]] != M[i][1]\
            and A[M[i][1]] != M[i][2]:
            ANS+=M[i]
            break

    AA = [str(i+1) for i in ANS]

    print(" ".join(AA))

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    a = []
    for _ in range(N):
        a.append(int(input))
    ans = str(range(1,N+1))
    for i in range(N+1):
        if str(i+1) in ans == a[i]:
            ans[i+1], ans[i+2] = ans[i+2], ans[i+1]
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in range(n):
    a = A[i]
    if i+1 != a:
      ukeire[a-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while can:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
      if can:
        s = heapq.heappop(can)
        L.append(s)
        heapq.heappush(can, t)
      else:
        temp = [t]
        while True:
          a = L.pop()
          temp.appned(a)
          for i in (temp[:-2] + temp[-1]):
            if A[L[-1]-1] != i:
              L.append(i)
              can = [j for j in temp if j != i]
              heapq.heapify(can)
              break
          else:
            continue
          break
    else:
      L.append(t)
  print(*L)

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
aa = list(map(int, input().split()))
aaa = deque(zip(range(1, N+1), aa))
tmp = deque()
ans = deque()
bef = ""

if aa == [2,1]:
    print(-1)
    exit(0)
elif set(aa[:-1]) == set((N,)):
    if aa[-1] == 1:
        tttttt = aaa.pop()
        aaa.append((tttttt[0], 2))
        flag = True
    else:
        flag = False
    for _ in range(N):
        now = aaa.pop()
        # print(aaa, ans,now, bef)
        try:
            next_ = aaa[-1][1]
        except:
            next_ = ""
        while bef == now[1] or next_ == now[0]:
            tmp.appendleft(now)
            print(ans)
            now = aaa.pop()
            try:
                next_ = aaa[-1][1]
            except:
                next_ = ""
        aaa += tmp
        tmp.clear()
        ans.appendleft(now[0])
        bef = now[0]
    if flag:
        ans[1] = 2
        ans[2] = 1
else:
    for _ in range(N):
        now = aaa.pop()
        while bef == now[1]:
            tmp.appendleft(now)
            now = aaa.pop()
        aaa += tmp
        tmp.clear()
        ans.appendleft(now[0])
        bef = now[0]

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
aa = list(map(int, input().split()))
aaa = deque(zip(range(1, N+1), aa))
tmp = deque()
ans = deque()
bef = ""

if aa == [2,1]:
    print(-1)
    exit()
elif set(aa[:-1]) == set((N,)):
    if aa[-1] == 1:
        tttttt = aaa.pop()
        aaa.append((tttttt[0], 2))
        flag = True
    else:
        flag = False
    for _ in range(N):
        now = aaa.pop()
        # print(aaa, ans,now, bef)
        try:
            next_ = aaa[-1][1]
        except:
            next_ = ""
        while bef == now[1] or next_ == now[0]:
            tmp.appendleft(now)
            print(ans)
            now = aaa.pop()
            try:
                next_ = aaa[-1][1]
            except:
                next_ = ""
        aaa += tmp
        tmp.clear()
        ans.appendleft(now[0])
        bef = now[0]
    if flag:
        ans[1] = 2
        ans[2] = 1
else:
    for _ in range(N):
        now = aaa.pop()
        while bef == now[1]:
            tmp.appendleft(now)
            now = aaa.pop()
        aaa += tmp
        tmp.clear()
        ans.appendleft(now[0])
        bef = now[0]

print(*ans)

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in range(n):
    a = A[i]
    if i+1 != a:
      ukeire[a-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while can:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
      if can:
        s = heapq.heappop(can)
        L.append(s)
        heapq.heappush(can, t)
      else:
        temp = [t]
        while True:
          a = L.pop()
          temp.appned(a)
          for i in sorted(temp):
            if A[L[-1]-1] != i:
              L.append(i)
              can = [j for j in temp if j != i]
              heapq.heapify(can)
              break
          else:
            continue
          break
    else:
      L.append(t)
  print(*L)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n=I()
a=LI()
ng=[[] for i in range(n)]

q=[1]
r=list(range(-n,-1))
heapify(r)

for i in range(n-1):
    if r:
        0
    else:
        break
    nx=-r[-1]
    #show(nx,q[-1],q,r)
    if a[q[-1]-1]==nx:
        forb=-r.pop()
        cand=-r.pop()
        q.append(cand)
        heappush(r,-forb)
    else:
        q.append(-r.pop())
    
print(*q)

Submission status: Runtime Error

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
def solve(x,flag):
    a,b = [i+1 for i in range(N)],0
    a[x-1] = 10**9+7
    ans = [x]
    taboo = A[x-1]
    heapq.heapify(a)
    ans0 = ""
    for i in range(N-1):
        p = heapq.heappop(a)
        if taboo == p:
            b = p
            p = heapq.heappop(a)
        ans.append(p)
        if p >= N+10:
            if flag:
                flag = False
                return solve(b,False)
            else:
                return -1
        taboo = A[p-1]
        if b:
            heapq.heappush(a,b)
            b = 0
    return ans
print(*solve(1,True))

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in range(n):
    a = A[i]
    if i+1 != a:
      ukeire[a-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while can:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
      if can:
        s = heapq.heappop(can)
        L.append(s)
        heapq.heappush(can, t)
      else:
        temp = [t]
        while True:
          a = L.pop()
          temp.appned(a)
          for i in temp:
            if A[L[-1]-1] != i:
              L.append(i)
              can = [j for j in temp if j != i]
              heapq.heapify(can)
              break
          else:
            continue
          break
    else:
      L.append(t)
  print(*L)

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in range(n):
    a = A[i]
    if i+1 != a:
      ukeire[a-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while can:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
      if can:
        s = heapq.heappop(can)
        L.append(s)
        heapq.heappush(can, t)
      else:
        temp = [t]
        while True:
          a = L.pop()
          temp.appned(a)
          for i in temp:
            if A[L[-1]-1] != i:
              L.append(i)
              can = [j for j in temp if j != i]
              break
          else:
            continue
          break
    else:
      L.append(t)
  print(*L)

Submission status: Runtime Error

Solution code:
import sys

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
ans[0]=1
suuzi=[i for i in range(2,n+1) ]
for i in range(1,n):
    suuzi.sort()
    if suuzi == []:
        print('-1')
        sys.exit()
    ans[i]=suuzi[0]
    if ans[i]==a[ans[i-1]-1]:
        ans[i]=suuzi[1]
    suuzi.remove(ans[i])
        
for i in range(len(ans)):
    print(ans[i], end=' ')

Submission status: Runtime Error

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=[0]+a[:-1]
ls=[0]
nokori=[k for k in range(1,N+1)]
for i in range(N):
  flag=False
  for j in range(N-i):#残りの小さい数字から
    if nokori[j]!=b[ls[-1]]:
      ls.append(nokori[j])
      nokori.pop(j)
      flag=True
      break
  if flag==False:
    print(-1)
    exit()
print(ls[1:])

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))

if n==2 and a==[2,1]: print(-1),sys.exit()

x=[i+2 for i in range(n-1)]
ans=[1]
print(x)
for i in range(n-1):
    tmp=ans[-1]-1
    if a[tmp]!=x[0]:
        ans.append(x.pop(0))
    elif i==n-1: ans.append(x.pop(0))
    else: ans.append(x.pop(1))

for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in range(n):
    a = A[i]
    if i+1 != a:
      ukeire[a-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while can:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
      s = heapq.heappop(can)
      L.append(s)
      heapq.heappush(can, t)
    else:
      L.append(t)
  print(*L)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
if n==2 and a==[2,1]: print(-1),sys.exit()
x=[i+2 for i in range(n-1)]
ans=[1]
for i in range(n-1):
    tmp=ans[-1]-1
    if a[tmp]!=x[0]:
        ans.append(x.pop(0))
    else: ans.append(x.pop(1))

for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
num=[i for i in range(1,n+1)]
for i in range (n-1):
    if a[i]==num[i+1] and num[i]==i+1:
        t=num[i+1]
        num[i+1]=num[i+2]
        num[i+2]=t
for i in range(n):
    print(num[i],end=" ")

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a = input().split()
dict_set = {}
for i in range(1, n + 1):
    dict_set[str(i)] = a[i-1]

def func(suuzi, check_list, not_check_list):
    if len(check_list) == n:
        ans = " ".join(check_list)
        return ans
    else:
        j = 1
        for i in not_check_list:
            if dict_set[suuzi] == str(i):
                j += 1
                continue
            ans = func(str(i), check_list + [str(i)], not_check_list[:(j-1)] + not_check_list[j:])
            if ans != "-1":
                return ans
            j += 1
        return "-1"

not_check_list = list(range(1, n + 1))
for i in range(1, n + 1):
    check_list = [str(i)]
    ans = func(str(i), check_list, not_check_list[:(i-1)] + not_check_list[i:])
    if ans != "-1":
        break
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
ukeire = [0]*n
A = list(map(int, input().split()))
if n==2 and A == [2, 1]:
  print(-1)
else:
  for i in A:
    ukeire[i-1] += 1
  f = 1
  if n-1 in ukeire:
    f = ukeire.index(n-1) + 1
  can = [i+1 for i in range(n) if i != f-1]
  heapq.heapify(can)
  L = [f]
  while can:
    t = heapq.heappop(can)
    if A[L[-1]-1] == t:
      s = heapq.heappop(can)
      L.append(s)
      heapq.heappush(can, t)
    else:
      L.append(t)
  print(*L)

Submission status: Runtime Error

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

import itertools
from collections import deque
from heapq import heappop, heappush, heapify
from collections import defaultdict

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return False

if N <= 6:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

in_deg = [0] * (N+10)
for x in A:
    in_deg[x] += 1

q = [(-x, i) for i,x in enumerate(in_deg)] # in_deg最大の人を分かるようにしたい
heapify(q)
se = set(q)

def greedy(rest,A,ng_first):
    B = []
    ng = ng_first
    while len(rest) >= 4:
        x = rest[0]; y = rest[1]
        if ng == x:
            B.append(y)
            rest.popleft()
            rest.popleft()
            rest.appendleft(x)
        else:
            B.append(x)
            rest.popleft()
        ng = A[B[-1]]
    return B

rest = deque(range(N))
B = []
prev = N
n = N
for _ in range(N-4):
    while q[0] not in se:
        heappop(q)
    if -q[0][0] == n - 1:
        v = q[0][1]
        B.append(v)
        rest.remove(v)
        B += greedy(rest, A, A[B[-1]])
        print(-1)
        exit()
        break
    x = rest[0]; y = rest[1]
    if A[prev] == x:
        B.append(y)
        rest.popleft()
        rest.popleft()
        rest.appendleft(x)
    else:
        B.append(x)
        rest.popleft()
    prev = B[-1]
    v = A[B[-1]]
    se.remove((-in_deg[v],v))
    in_deg[v] -= 1
    se.add((-in_deg[v],v))
if len(B) < N:
    B += list(solve_small(rest, A, A[B[-1]]))

print(' '.join(str(x+1) for x in B))

Submission status: Runtime Error

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

import itertools
from collections import deque
from heapq import heappop, heappush, heapify
from collections import defaultdict

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return False

if N <= 6:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

in_deg = [0] * (N+10)
for x in A:
    in_deg[x] += 1

q = [(-x, i) for i,x in enumerate(in_deg)] # in_deg最大の人を分かるようにしたい
heapify(q)
se = set(q)

def greedy(rest,A,ng_first):
    B = []
    ng = ng_first
    while len(rest) >= 4:
        x = rest[0]; y = rest[1]
        if ng == x:
            B.append(y)
            rest.popleft()
            rest.popleft()
            rest.appendleft(x)
        else:
            B.append(x)
            rest.popleft()
        ng = A[B[-1]]
    return B

rest = deque(range(N))
B = []
prev = N
n = N
for _ in range(N-4):
    while q[0] not in se:
        heappop(q)
    if -q[0][0] == n - 1:
        v = q[0][1]
        B.append(v)
        rest.remove(v)
        B += greedy(rest, A, A[B[-1]])
        break
    x = rest[0]; y = rest[1]
    if A[prev] == x:
        B.append(y)
        rest.popleft()
        rest.popleft()
        rest.appendleft(x)
    else:
        B.append(x)
        rest.popleft()
    prev = B[-1]
    v = A[B[-1]]
    se.remove((-in_deg[v],v))
    in_deg[v] -= 1
    se.add((-in_deg[v],v))
if len(B) < N:
    B += list(solve_small(rest, A, A[B[-1]]))

print(' '.join(str(x+1) for x in B))

Submission status: Runtime Error

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

import itertools
from collections import deque
from heapq import heappop, heappush, heapify
from collections import defaultdict

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return False

if N <= 4:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

in_deg = [0] * (N+10)
for x in A:
    in_deg[x] += 1

q = [(-x, i) for i,x in enumerate(in_deg)] # in_deg最大の人を分かるようにしたい
heapify(q)
se = set(q)

def greedy(rest,A,ng_first):
    B = []
    ng = ng_first
    while len(rest) >= 4:
        x = rest[0]; y = rest[1]
        if ng == x:
            B.append(y)
            rest.popleft()
            rest.popleft()
            rest.appendleft(x)
        else:
            B.append(x)
            rest.popleft()
        ng = A[B[-1]]
    return B

rest = deque(range(N))
B = []
prev = N
n = N
for _ in range(N-4):
    while q[0] not in se:
        heappop(q)
    if -q[0][0] == n - 1:
        v = q[0][1]
        B.append(v)
        rest.remove(v)
        B += greedy(rest, A, A[B[-1]])
        break
    x = rest[0]; y = rest[1]
    if A[prev] == x:
        B.append(y)
        rest.popleft()
        rest.popleft()
        rest.appendleft(x)
    else:
        B.append(x)
        rest.popleft()
    prev = B[-1]
    v = A[B[-1]]
    se.remove((-in_deg[v],v))
    in_deg[v] -= 1
    se.add((-in_deg[v],v))
if len(B) < N:
    B += list(solve_small(rest, A, A[B[-1]]))

print(' '.join(str(x+1) for x in B))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n == 2 and a[0] == 2 and a[1] == 1:
    exit(1)
print(-1)