D. Secret Santa(构造)

首先n点n边，是一个基环树，

可以观察得到其实最大值是不变的

剩下的人自己随便找个人匹配即可

所以关键是构造一个方案解决匹配到自己的情况

找到所有没送出礼物的人，然后直接匹配，如果匹配到自己

因为没有送出礼物的人想送出礼物的人被选了，才没送出

所以可以换一下，让当前这个没送出礼物的人送给想送出礼物的目标，然后让原本送给目标的人怂给当前这个没有送出礼物的人即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,m;
vector<int> g[N];
int a[N];
int vis[N],mach[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vis[i]=0;
        mach[i]=0;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(vis[a[i]]) continue;
        vis[a[i]]=i;
        mach[i]=a[i];
        ans++;
    }
    cout<<ans<<"\n";
    vector<int> res;
    for(int i=1;i<=n;i++){
        if(vis[i]==0) res.push_back(i);
    }
    int p=1;
    //mach第i个人喜欢的那个人 vis a[i]选的人的编号
    for(auto it:res){
        while(mach[p]) p++;//
        mach[p]=it;
        if(p==it){
            swap(mach[p],mach[vis[a[p]]]);
            vis[a[p]]=p;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<mach[i]<<" ";
    }
    cout<<"\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}