Chef has $N$ markers. There is a cap on each marker. For each valid $i$, the $i$-th marker has colour $a_i$. Initially, for each valid $i$, the colour of the cap on the $i$-th marker is also $a_i$.
Chef wants to rearrange the caps in such a way that no marker has the same colour as its cap. (Obviously, each marker must have exactly one cap.) Can he do that? If he can, find one such way to rearrange the caps. If there are multiple solutions, you may find any one.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$.

-----Output-----
- For each test case:
- If Chef cannot successfully rearrange the caps, print a single line containing the string "No" (without quotes).
- Otherwise, print two lines. The first line should contain the string "Yes" (without quotes). The second line should contain $N$ space-separated integers describing a valid rearrangement of caps. For each valid $i$, the $i$-th of these integers should denote the final colour of the cap on the $i$-th marker.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^5$
- $1 \le a_i \le 10^9$ for each valid $i$

-----Example Input-----
2
9
1 1 1 2 2 2 3 3 3
2
1 1

-----Example Output-----
Yes
2 2 2 3 3 3 1 1 1
No

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from collections import Counter,defaultdict

for i in range(int(input())):
 n=int(input())
 arr=list(map(int,input().split()))
 coun=Counter(arr)
 check=True

 for j in coun:
  if coun[j]>n//2:
   print("No")
   check=False
   break




 if check==True:
  print("Yes")
  narr=sorted(arr)
  dic=defaultdict()
  j=0
  for j in range(len(narr)):
   if narr[j] not in dic:
    dic[narr[j]]=j
  ans=[0]*n
  for j in range(len(arr)):
   ans[j]=narr[(dic[arr[j]]+n//2)%n]
   if coun[arr[j]]!=1:
    dic[arr[j]]+=1
  print(*ans)


# cook your dish here
t=int(input())
for _ in range(t):
 n=int(input())
 a=list(map(lambda x: int(x), input().split()))
 b=[]
 for i in range(0,len(a)):
  b.append((a[i],i))
 b.sort(key=lambda x:x[0])
 hashmap={}
 maximum=0
 for i in range(0,len(a)):
  if a[i] not in hashmap:
   hashmap[a[i]]=0
  hashmap[a[i]]+=1
  if hashmap[a[i]]>maximum:
   maximum=hashmap[a[i]]
 if maximum>n-maximum:
  print("No")
 else:
  print("Yes")
  c=[]
  for i in range(0,len(b)):
   c.append(b[(i+maximum)%n])
  d=[0 for _ in range(n)]
  for i in range(0,len(b)):
   d[b[i][1]]=c[i][0]
  for i in d:
   print(i,end=" ")
  print()


for q in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 d=[]
 for i in range(len(l)):
  d.append((l[i],i))
 l.sort()
 d.sort()
 i=0
 count=[]
 while i<n:
  x=l[i]
  j=0
  c=0
  while i+j<n and l[i+j]==x:
   c+=1
   j+=1
  count.append(c)
  i+=j
 c=max(count)
 if c>n//2:
  print('No')
 else:
  ans=[0]*n
  for i in range(len(l)):
   ans[d[i][1]]=d[i-c][0]
  print('Yes')
  print(*ans)


# cook your dish here
from collections import Counter

tc = int(input())

while tc>0:
 n=int(input())
 lis=list(map(int, input().split()))
 l1 = [(x,y) for y,x in enumerate(lis)]
 lis.sort()
 l1.sort()
 i=0
 c_l=[]
 while i<n:
  x=lis[i]
  j=0
  c=0
  while i+j<n and lis[i+j]==x:
   c+=1
   j+=1
  c_l.append(c)
  i+=j
 c=max(c_l)
 if c>n//2:
  print('No')
 else:
  ans=[0]*n
  for i in range(len(lis)):
   ans[l1[i][1]]=l1[i-c][0]
  print('Yes')
  print(*ans)
 tc-=1


for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 l1=[(x,i) for i,x in enumerate(l)]
 l.sort()
 l1.sort()
 i=0
 count=[]
 while i<n:
  x=l[i]
  j=0
  c=0
  while i+j<n and l[i+j]==x:
   c+=1
   j+=1
  count.append(c)
  i+=j
 c=max(count)
 if c>n//2:
  print('No')
 else:
  ans=[0]*n
  for i in range(len(l)):
   ans[l1[i][1]]=l1[i-c][0]
  print('Yes')
  print(*ans)


from collections import defaultdict
def caps(a):
 d=defaultdict(list)
 for i in range(len(a)):
  d[a[i]].append(i)
  if(len(d[a[i]])>len(a)//2):
   return('No',[])
 arr=[]
 for i in d.keys():
  arr+=([i]*len(d[i]))
 arr2=[i for i in arr]
 arr2=arr2[len(a)//2:]+arr2[:len(a)//2]
 for i in range(len(arr2)):
  di=arr[i]
  vi=arr2[i]
  a[d[di][0]]=vi
  d[di].remove(d[di][0])
 return('Yes',a)

t=int(input())
for _ in range(t):
 n=input()
 a=input().split()
 ans,arr=caps(a)
 print(ans)
 if(ans=='Yes'):
  st=""
  for i in arr:
   st+=i+' '
  print(st)

# cook your dish here
for z in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 dict_count = {}
 for num in a:
  if num in dict_count:
   dict_count[num]+=1
  else:
   dict_count[num]=1
 possible = 1
 for key in dict_count:
  if dict_count[key]>n//2:
   possible=0
   break
 if possible:
  print('Yes')
  a_index = [(a[i],i) for i in range(n)]
  a_index.sort()
  cap_dict = {i:-1 for i in range(n)}
  h = n//2
  for i in range(n):
   cap_dict[a_index[i][1]] = a_index[(i+h)%n][0]
  caps = [str(cap_dict[i]) for i in range(n)]
  print(' '.join(caps))
 else:
  print('No')

R = lambda: map(int, input().split())
for _ in range(int(input())):
 n = int(input())
 L1 = list(R())
 L = sorted(L1)
 d = {}
 f = 0
 p = n//2
 for i in range(n):
  if L[i] not in d:d[L[i]] = [0, []]
  d[L[i]][0] += 1
  d[L[i]][1] += [i]
  if d[L[i]][0] > p:f = 1;break
 if f:print("No")
 else:
  print("Yes")
  res = []
  #print(d)
  for i in L1:
   ind = d[i][1].pop()
   if n%2 and ind == n-1:
    res.append(L[0])
    continue
   if ind+p < n:
    res.append(L[ind+p])
   elif ind-p >= 0:
    res.append(L[ind-p])
  print(*res)

t=int(input())
for _ in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 f={}
 poss=1
 A=[[a[i],i] for i in range(n)]
 for i in range(n):
  if(a[i] in f):
   f[a[i]]+=1
  else:
   f[a[i]]=1
 for i in list(f.values()):
  if(i>n//2):
   poss=0
 if(poss):
  A.sort()

  ans=[0]*n
  j=max(f.values())
  B=A[j:]+A[:j]
  
  for i in range(n):
   ans[A[i][1]]=B[i][0]

  print("Yes")
  print(*ans)
 else:
  print("No")



t=int(input())
for _ in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 f={}
 poss=1
 A=[[a[i],i] for i in range(n)]
 for i in range(n):
  if(a[i] in f):
   f[a[i]]+=1
  else:
   f[a[i]]=1
 for i in list(f.values()):
  if(i>n//2):
   poss=0
 if(poss):
  A.sort()

  ans=[0]*n
  j=max(f.values())
  B=A[j:]+A[:j]
  
  for i in range(n):
   ans[A[i][1]]=B[i][0]

  print("Yes")
  print(*ans)
 else:
  print("No")



# cook your dish here
from collections import Counter as cp
t=int(input())
for i in range(t):
 n=int(input())
 p=input().split()
 l=cp(p)
 r=int(n/2)
 if l.most_common(1)[0][1]<=r:
  print('Yes')
 else:
  print('No')
  continue
 counter_list=[]
 t_list=[]
 for j in range(n):
  counter_list.append(int(p[j]))
  t_list.append((j,int(p[j])))
 t_list.sort(key=lambda x: x[1])
 #print(t_list)
 for k in range(n):
  q=t_list[k]
  # print(q)
  s=t_list[(k+r)%n]
  #print(s)
  counter_list[q[0]]=s[1]
 for k in range(n-1):
  print(counter_list[k],end=' ')
 print(counter_list[n-1])

from collections import Counter
from copy import copy
import random


def derange(arr, max_freq):
 new_arr = copy(arr)
 dis = []
 for index, item in enumerate(new_arr):
  dis.append((item, index))

 dis.sort()
 item, index = [a for a, b in dis], [b for a,b in dis]

 item = item[-max_freq: ] + item[:-max_freq]

 dis = list(zip(item, index))
 new_arr = [0] * len(new_arr)
 for a, b in dis:
  new_arr[b] = a

 return new_arr

for _ in range(int(input())):
 n = int(input())
 arr = list(map(int, input().split()))

 freq = Counter(arr)
 flag = 1
 val = list(freq.values())
 for i in val:
  if 2 * i > n:
   flag = 0

 if flag != 0:
  print("Yes")
  new = derange(arr, max(val))
  print(*new)
 else:
  print("No")


# cook your dish here
from collections import Counter
for z in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 b=[]
 for j in range(n):b.append((a[j],j))
 c=Counter(a)
 m=0
 for x,y in c.items():
  m=max(y,m)
 if m>n-m:
  print("No")
 else:
  d=[0]*n
  b.sort()
  for i in range(n):
   d[b[i][1]]=b[i-m][0]
  print("Yes")
  for i in d:print(i,end=" ")
  print()
   



t = int(input())

for i in range(t):
 n = int(input())
 hash = {}
 l = list(map(int,input().split()))
 for j in range(n):
  try:
   hash[l[j]]
  except:
   hash[l[j]] = 1
  else:
   hash[l[j]]+=1
 flag = 0
 max = 0
 for j in range(n):

  if hash[l[j]]>n//2:
   flag = 1
   break
  elif hash[l[j]]>max:
   max = hash[l[j]]
 # l.sort()
 # print(max)
 # print(l)
 v = sorted(range(len(l)),key=lambda k:l[k])
 u = sorted(l)
 ans = [0]*n
 if flag == 0:
  print('Yes')
  z = u[max:] + u[:max]
  for i in range(n):
   ans[v[i]] = z[i]

  print(*ans)
 else:
  print('No')

# cook your dish here
 # print("Odd")    
from collections import Counter

for _ in range(int(input())):

 n = int(input())
 li = [int(x) for x in input().split()]
 # n = 2
 # li  = [1,1]

 inp_ord = list(enumerate(li))
 cow = Counter(li)
 max_freq = cow.most_common(1)[0][1]

 if max_freq > n - max_freq:
  print("No")

 else:
  sorted_input = sorted(inp_ord, key= lambda x : x[1])

  foo = n- max_freq
  for i in range(foo):

   current_element = sorted_input[i][1]
   curr_pos =sorted_input[i][0]

   toSwapIndex = i + max_freq

   swap_partner = sorted_input[toSwapIndex][1] 
   swap_position = sorted_input[toSwapIndex][0]

   sorted_input[i] = curr_pos, swap_partner
   sorted_input[toSwapIndex] = swap_position, current_element

  op_list = sorted(sorted_input, key = lambda x : x[0])
  bar = [y for x, y in op_list]
  print("Yes")
  print(*bar)




for test in range(int(input())):
 n=int(input())
 arr=list(map(int,input().split()))
 mp=[]
 for i in range(n):
  mp.append([arr[i],i])
 mp.sort(key=lambda x:x[0])
 prev=-1
 max=-1
 count=1
 for i in range(n):
  if prev==mp[i][0]:
   count+=1
  else:
   count=1
  if count>max:
   max=count
  prev=mp[i][0]
 if 2*max>n:
  print("No")
 else:
  print("Yes")
  x=[0]*n
  for i in range(n):
   x[(i+max)%n]=mp[i][0]
  y=[0]*n
  for i in range(n):
   y[mp[i][1]]=x[i]
  for i in range(n):
   print(y[i],end=' ')
  print()


t=int(input())
for tt in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 d={}
 for i in a:
  if i in d:
   d[i]+=1
  else:
   d[i]=1
 arr=[]
 mm=0
 for key,value in d.items():
  mm=max(mm,value)
 for i in range(len(a)):
  arr.append([a[i],i])
 ans=[0]*(n)
 if mm>(n//2):
  print("No")
 else:
  print("Yes")
  arr=sorted(arr,key=lambda item:item[0])
  for i in range(n):
   ans[arr[(i+mm)%n][1]]=arr[i][0]
  for i in ans:
   print(i,end=" ")
  print()

for _ in range(int(input())):
   n=int(input())
   dct={}
   l=list(map(int,input().split()))
   for i in range(n):
     if l[i] in dct:
       dct[l[i]].append(i)
     else:
       dct[l[i]]=[i]
   d2={}
   flag=True
   m=0
   for i in dct:
     d2[i]=len(dct[i])
     m=max(m,d2[i])
   if(m>n//2):
     print("No")
     continue
   k=list(d2.keys())
   def fun(itm):
     nonlocal d2
     return d2[itm]
   k.sort(key=fun,reverse=True)
   ans=[None]*n
   j=len(k)
   rem=[None]*j
   place=[0]*j
   for i in range(j):
     rem[i]=d2[k[i]]
   ch=1
  # print(k)
   for i in range(j):
     while(d2[k[i]]!=0):
       d2[k[i]]-=1
       if(rem[ch]==0):
         ch=(ch+1)%j
       ans[dct[k[i]][place[i]]]=k[ch]
       place[i]+=1
       rem[ch]-=1
      #     print(ans)
   print("Yes")
   for i in ans:
     print(i,end=" ")
   print("")

'''
25th march 2019 monday
rocket to the moon
'''

t = int(input())
for _ in range(t):
 n = int(input())
 a = [int(x) for x in input().split()]
 
 b = list()
 for id, x in enumerate(a):
  b.append([x, id])

 b.sort()
 a.sort()
 counter = list()
 count = 1
 c_max = 1
 for i in range(1, n):
  if a[i] == a[i - 1]:
   count += 1
  else:
   counter.append(count)
   c_max = max(c_max, counter[-1])
   count = 1
 counter.append(count)
 c_max = max(c_max, counter[-1])
 if c_max > n//2:
  print("No")
 else:
  print("Yes")
  c = [0] * n
  for i in range(n):
   c[b[i][1]] = b[(i + c_max)%n][0]
  for x in c:
   print(x, end=' ')
  print('')


  






# cook your dish here
T = int(input()) 
for i in range(T) :
 N = int(input()) 
 L = list(map(int, input().split()))
 M = list(range(1,N+1)) 
 Z = [0] * N
 L, M = (list(t) for t in zip(*sorted(zip(L, M))))
 cout = (N + 1)//2
 mybool = True 
 for i in range(N) :
  Z[i] = L[(i + cout) % N]
  if (Z[i] == L[i]) :
   print("No")
   mybool = False 
   break 
 if mybool :
  print("Yes") 
  M, Z = (list(t) for t in zip(*sorted(zip(M, Z))))
  for i in range(N):
   print(Z[i], end = " ") 
  print() 
 # print(M) 
 # print(L) 
 # print(Z) 



for _ in range(int(input())):
 n=int(input())
 d={};b=[0]*n;g={};h={}
 a=list(map(int,input().split()))
 for i in range(n):
  if a[i] in d:
   d[a[i]]+=1
   h[a[i]].append(i)
  else:
   d[a[i]]=1
   h[a[i]]=[i]
 x=list(map(list,sorted(list(d.items()),key=lambda y:y[1])))
 #print(x)
 l=0;r=len(x)-1
 
 for i in d:
  g[i]=[]
 
 while l<r:
  if x[r][1]>=x[l][1]:
   g[x[r][0]].append([x[l][0],x[l][1]])
   g[x[l][0]].append([x[r][0],x[l][1]])
   x[r][1]-=x[l][1]
   x[l][1]=0
   l+=1
  else:
   if x[r][1]>0:
    g[x[r][0]].append([x[l][0],x[r][1]])
    g[x[l][0]].append([x[r][0],x[r][1]])
    x[l][1]-=x[r][1]
    x[r][1]=0
   r-=1
 #print(g)
 s=[];m=x[-1][0];k=-1
 for i in range(n):
  if g[a[i]]!=[]:
   b[i]=g[a[i]][-1][0]
   g[a[i]][-1][1]-=1
   if g[a[i]][-1][1]==0:
    g[a[i]].pop()
  else:
   s.append(i);k=a[i]
 #print(b)
 if k==m:
  print('No')
 else:
  for i in h[m]:
   if b[i]!=k:
    if s!=[]:
     b[s.pop()]=b[i]
     b[i]=k
  print('Yes')
  print(*b)
  


for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 b=[[a[i],i]for i in range(n)]
 b.sort()
 c=[0]*n
 #print(b)
 for i in range(n):
  x=b[i][0]
  #print(c)
  #print(a,x,b[(i + (n//2))%n][1])
  if a[b[(i + (n//2))%n][1]]==x:
   print("No")
   break
  else:
   
   c[b[(i + (n//2))%n][1]]=x
 else:
  print("Yes")
  print(*c)


def arrange(n,l):
 list1=[0]*n;i=0
 list2=[-1]*n
 for j in range(n):
  if i!=j:
   if i<n and list1[i]==1:
    for k in range(i,n):
     i+=1
     if i<n and list1[i]!=1:break
   if i==n:break
   else:
    if l[j]!=l[i]:
     list2[i]=l[j]
     list2[j]=l[i]
     list1[i]=1;list1[j]=1
     i+=1
 if i!=n:
  for j in range(0,i):
   if i<n and list1[i]==1:
    for k in range(i,n):
     i+=1
     if i<n and list1[i]!=1:break
   if i==n:break
   else:
    if l[j]!=l[i] and list2[j]!=l[i]:
     list2[i]=list2[j]
     list2[j]=l[i]
     list1[i]=1
     i+=1
 if i!=n:print('No')
 else:
  print('Yes')
  for j in list2:
   print(j,end=' ')
  print()

t=int(input())
for i in range(t):
 N=int(input())
 l=[]
 s=input().split(' ')
 for j in range(N):
  l.append(int(s[j]))
 arrange(N,l)