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

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d
左からおいていくことを考える
残ったカード全てから嫌われている場合、もう置くしかない
貪欲に置いていき、残りカード全てから嫌われてしまったら置く？

そうなるとただの実装難問題だが…

for i in range(N)
    if 残りのカード全てから嫌われてしまっているカードがあったら置く。
    elif 辞書順最小のカードが置けたら置く
    elif 辞書順2番目のカードが存在したら置く。
    else -1?

なのか？？
3枚以上なら絶対置くことが可能そうに見える


残りのカード全てから嫌われてしまっている、判定はどうすればよいと？
嫌われてる辞書(残存するカードのみ)を作っておき、len(辞書) == 2 で、1でない方が嫌われ者

elif 以降はheapqを使うのが良さそう
おいてるフラグ配列を管理しておき、置いてないが出るまでpop
置けない場合は、もう1つ出るまでpopし、置いて最初の奴を戻す

何が問題なんだ…？
この方法だとqueueが空になってしまうけど構成不可能ではない、ケースが存在する
N==2で-1は正しかった
互いに嫌いな2個が最後に残るとまずい
→最後の3つを全探索するか？
→これが丸そう
"""

def allserch(dnt,x,y,z):

    ret = []
    if dnt != x and a[x] != y and a[y] != z:
        ret.append([x,y,z])
    if dnt != x and a[x] != z and a[z] != y:
        ret.append([x,z,y])
    if dnt != y and a[y] != x and a[x] != z:
        ret.append([y,x,z])
    if dnt != y and a[y] != z and a[z] != x:
        ret.append([y,z,x])
    if dnt != z and a[z] != x and a[x] != y:
        ret.append([z,x,y])
    if dnt != z and a[z] != y and a[y] != x:
        ret.append([z,y,x])
    ret.sort()
    return ret[0]


import heapq
import sys

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

if N == 2:
    print (-1)
    sys.exit()

for i in range(N):
    a[i] -= 1

ans = []
dont = None

hq = []
for i in range(N):
    heapq.heappush(hq,i)
    
usable = [True] * N
dic = {}
for i in range(N):
    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1


for loop in range(N-3):

    flag = True
    
    if len(dic) == 2:
        maxind = None

        for i in dic:
            if maxind == None:
                maxind = i
            elif dic[i] > dic[maxind]:
                maxind = i

        if dic[maxind] == (N-loop-1) and usable[maxind]:
            nc = maxind
            flag = False

    if flag:

        while (not usable[hq[0]]):
            heapq.heappop(hq)
            
        fi = heapq.heappop(hq)
        if dont != fi:
            nc = fi
        else:

            while (not usable[hq[0]]):
                heapq.heappop(hq)

            
            sec = heapq.heappop(hq)
            heapq.heappush(hq,fi)
            nc = sec

    
    ans.append(nc+1)
    usable[nc] = False
    dic[a[nc]] -= 1
    dont = a[nc]
    if dic[a[nc]] == 0:
        del dic[a[nc]]

pas = []
while len(hq) > 0:
    now = heapq.heappop(hq)
    if usable[now]:
        pas.append(now)

rec = allserch(dont,pas[0],pas[1],pas[2])
for i in range(3):
    rec[i] += 1
ans += rec

print (*ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, k):
        if k > self.total:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        
        
        
        return now_index


n = I()
A = LI()
if n == 2:
    if A[0] == 2 and A[1] == 1:
        print(-1)
    elif A[0] != 2:
        print(1, 2)
    else:
        print(2, 1)
    exit()


bit  = BIT(n + 1)
for i in range(1, n + 1):
    bit.add(i, 1)


ans = []
pre = -1
for j in range(n - 1):
    x = bit.search(1)
    if x == pre:
        x = bit.search(2)
    bit.add(x, -1)
    ans += [x]
    pre = A[x - 1]

last_x = bit.search(1)
bit.add(last_x, -1)
if A[ans[-1] - 1] != last_x:
    ans += [last_x]
    print(*ans)
    exit()


cnt = 0
for k in range(n - 2, -1, -1):
    if A[ans[k] - 1] == last_x:
        x = ans.pop()
        bit.add(x, 1)
        cnt += 1
    else:
        break


if cnt == 1:
    last3 = []
    for a, b, c in permutations((ans.pop(), x, last_x)):
        if A[ans[-1] - 1] != a and A[a - 1] != b and A[b - 1] != c:
            last3 += [[a, b, c]]
    print(*ans + min(last3))
    exit()


ans += [last_x]
x = bit.search(1)
if x == A[ans[-1] - 1]:
    x = bit.search(2)
bit.add(x, -1)
ans += [x]
for l in range(cnt - 1):
    x = bit.search(1)
    bit.add(x, -1)
    ans += [x]
print(*ans)

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappop, heappush
from itertools import permutations
from operator import itemgetter












def fill_remainings(ans, aaa, x, remainings):
    """
    xを先頭にして残りを昇順に追加
    ただしxの次の要素のみ、aaa[x]で禁止されていた場合はその次と入れ替える
    remainingsにはxを含め3要素以上残っていることが前提
    """
    ans.append(x)
    i = len(ans)
    while remainings:
        k = heappop(remainings)
        if k != x:
            ans.append(k)
    if aaa[x] == ans[i]:
        ans[i], ans[i + 1] = ans[i + 1], ans[i]


def solve(n, aaa):
    if n == 2:
        return [-1]

    in_degrees = defaultdict(lambda: 0)
    for i, a in enumerate(aaa, start=1):
        in_degrees[a] += 1
    in_degrees = dict(in_degrees)

    
    
    curr_max = max(in_degrees.values())

    remainings = list(range(1, n + 1))

    aaa.insert(0, 0)

    ans = []
    banned = -1
    for i in range(n - 3):
        if curr_max == n - i - 1:
            curr_x, curr_max = max(in_degrees.items(), key=itemgetter(1))
            if curr_max == n - i - 1:
                fill_remainings(ans, aaa, curr_x, remainings)
                return ans
        top = heappop(remainings)
        if top == banned:
            ans.append(heappop(remainings))
            heappush(remainings, top)
        else:
            ans.append(top)
        banned = aaa[ans[-1]]
        
        if banned in in_degrees:
            if in_degrees[banned] == 1:
                del in_degrees[banned]
            else:
                in_degrees[banned] -= 1
        in_degrees.pop(ans[-1], 0)

    remainings.sort()
    for i, j, k in permutations(remainings):
        if i != banned and j != aaa[i] and k != aaa[j]:
            ans += [i, j, k]
            break

    return ans


n, *aaa = map(int, sys.stdin.buffer.read().split())
print(*solve(n, aaa))

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
A=[0]+list(map(int,input().split()))

if N==2 and A==[0,2,1]:
    print(-1)
    sys.exit()


C=[0]*(N+1)

for i in range(1,N+1):
    if A[i]!=i:
        C[A[i]]+=1

import heapq

H=[]
for i in range(1,N+1):
    H.append((-C[i],i))

heapq.heapify(H)
NOUSE=list(range(N,0,-1))
USELIST=[0]*(N+1)
ANS=[0]

for rest in range(N-1,2,-1):
    
    
    if -H[0][0]==rest and rest!=0:
        x,y=heapq.heappop(H)
        ANS.append(y)
        C[y]=0
        C[A[y]]-=1
        USELIST[y]=1

    else:
        for i in range(len(NOUSE)-1,-1,-1):
            if USELIST[NOUSE[i]]==0 and A[ANS[-1]]!=NOUSE[i]:
                x=NOUSE.pop(i)
                ANS.append(x)
                USELIST[x]=1
                C[x]=0
                C[A[x]]-=1
                break
            

    while C[H[0][1]]!=-H[0][0]:
        x,y=heapq.heappop(H)
        heapq.heappush(H,(-C[y],y))

    while NOUSE and USELIST[NOUSE[-1]]==1:
        NOUSE.pop()


NOUSE=[i for i in range(N+1) if USELIST[i]==0]

from itertools import permutations
REST=list(permutations(sorted(NOUSE[1:])))

if len(REST)==2:
    for x,y in REST:
        if A[ANS[-1]]!=x and A[x]!=y:
            ANS.extend([x,y])
            break

else:    
    for x,y,z in REST:
        if A[ANS[-1]]!=x and A[x]!=y and A[y]!=z:
            ANS.extend([x,y,z])
            break

print(*ANS[1:])

Solution (Python):
from itertools import permutations
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def check_s(res, ngi):
    if res[0] == ngi: return False
    for i in range(len(res) - 1):
        if res[i + 1] == ng[res[i]]:
            return False
    return True


def small(remain, ngi):
    for res in permutations(remain):
        if check_s(res, ngi): return res
    return [-2]


def delpop():
    while 1:
        i = heappop(hp)
        if not used[i]: return i


def next_i(ngi, cr):
    i = delpop()
    if i == ngi:
        ii = delpop()
        heappush(hp, i)
        i = ii
    ngj = ng[i]
    if used[ngj]: return i
    if indeg[ngj] < cr - 1: return i
    heappush(hp, i)
    return ngj

def main():
    
    
    ans = []
    ngi = -1
    cnt_remain = n
    for _ in range(n - 4):
        i = next_i(ngi, cnt_remain)
        ans.append(i)
        used[i] = True
        cnt_remain -= 1
        ngi = ng[i]
        indeg[ngi] -= 1
    
    remain = []
    while hp:
        i=heappop(hp)
        if used[i]:continue
        remain.append(i)
    ans += small(remain, ngi)
    ans = [x + 1 for x in ans]
    print(*ans)

n = II()
ng = LI1()
hp = list(range(n))
heapify(hp)
used = [False] * n
indeg = [0] * n
for k in ng: indeg[k] += 1
main()

Solution (Python):
import sys
from itertools import permutations
readline = sys.stdin.readline

from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    
    def __init__(self, A, B, issum = False):
        
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        
        return L2, C
    
    def leng(self):
        
        return self.count(self.X[-1])
    
    def count(self, v):
        
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def gets(self, v):
        
        v1 = v
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.sumtree[s+k] < v:
                s += k
                v -= self.sumtree[s]
            k //= 2
        if s == self.size:
            return self.leng()
        return self.count(self.X[s]) + (v1 - self.countsum(self.X[s]))//self.X[s]
    
    def addsum(self, i, x):
        
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)


N = int(readline())

A = list(map(int, readline().split()))
if N <= 8:
    ans = True
    for k in permutations(range(1, N+1)):
        for i in range(N-1):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            break
    else:
        ans = False
    if not ans:
        print(-1)
    else:
        print(*k)
else:
    dim = [0]*(N+1)
    for i in range(N):
        a = A[i]
        dim[a] += 1
    T = PMS(list(range(2, N+1)), list(range(2, N+1)))
    L = [1]
    for i in range(N-7):
        k = T.get(1)
        if A[L[-1]-1] == k:
            k = T.get(2)
        L.append(k)
        T.add(k, -1)
    rem = [T.get(i) for i in range(1, 7)]
    for k in permutations(rem):
        if A[L[-1]-1] == k[0]:
            continue
        for i in range(5):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            ans = L + list(k) 
            break
    else:
        L = L + list(k)
        ok = -1
        ng = N-5
        while abs(ok-ng) > 1:
            med = (ok+ng)//2
            C = Counter()
            for l in L[med:]:
                C[A[l-1]] += 1
            k, v = C.most_common()[0]
            if v == N-med-1 and k in L[med:]:
                ng = med
            else:
                ok = med
        C = Counter()
        for l in L[ng:]:
            C[A[l-1]] += 1
        k, _ = C.most_common()[0]
        L = L[:ng] + [k]
        
        
        
        S = set(range(1, N+1)) 
        for l in L:
            S.remove(l)
        S = list(S)
        T = PMS(S, S)
        LS = len(S)
        for _ in range(LS):
            k = T.get(1)
            if A[L[-1]-1] == k:
                k = T.get(2)
            L.append(k)
            T.add(k, -1)
            
        ans = L
    print(*ans)

Solution (Python):
import sys
from itertools import permutations
n = int(input())
a = [0] + list(map(int, input().split()))
if n == 2:
	print(-1)
	sys.exit()
used = [False for _ in range(n+1)]
hate = dict()
for x in a[1:]:
	if x in hate:
		hate[x] += 1
	else:
		hate[x] = 1
cur = 1
ng = 0
ans = []
while len(ans) < n-3:
	if len(hate) == 2:
		worst = False
		for k, v in hate.items():
			if v == n - len(ans) - 1 and not used[k]:
				worst = k
				break
		if worst:
			ans.append(k)
			used[k] = True
			ng = a[k]
			hate[a[k]] -= 1
			if hate[a[k]] == 0:
				del hate[a[k]]
			continue

	while used[cur]:
		cur += 1

	if cur == ng:
		cur_copy = cur+1
		while used[cur_copy]:
			cur_copy += 1
		ans.append(cur_copy)
		used[cur_copy] = True
		ng = a[cur_copy]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]
	else:
		ans.append(cur)
		used[cur] = True
		ng = a[cur]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]

yet = [i for i in range(1, n+1) if not used[i]]
for p in permutations(yet):
	if p[0] != ng and p[1] != a[p[0]] and p[2] != a[p[1]]:
		ans += list(p)
		break

print(*ans)

Solution (Python):
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)] 
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))
    n -= 1
if len(B) < N:
    B += list(solve_small(rest, A, A[B[-1]]))

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