#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class dinic{ //Dinic法 /* max_frow(スタート,ゴール) 最大フローを求める dinic(int n) 頂点数 add(from,go,容量) 辺の追加 */ public: struct ed{ int cap; //容量 int rev; //逆 int to; //行き先 }; vector > g; //頂点 vector level; //startからの距離 vector iter; //どこまで調べたか void bfs(int start){ int kari = start; level.clear(); level.assign(g.size(), -1); level[kari] = 0; queue q; q.push(kari); while (!q.empty()){ kari = q.front(); q.pop(); for (int i = 0; i0 && level[g[kari][i].to]<0){ level[g[kari][i].to] = level[kari] + 1; q.push(g[kari][i].to); } } } } int dfs(int g1, int v66, int f66){ //現在地、目的地、frow if (g1 == v66){ return f66; } /*いける場所をさがす*/ for (int &i = iter[g1]; i0){ int kari = 0; if (f66 == -1){ kari = dfs(g[g1][i].to, v66, g[g1][i].cap); } else{ kari = dfs(g[g1][i].to, v66, min(g[g1][i].cap, f66)); } if (kari == -1){ continue; } else{ g[g1][i].cap -= kari; g[g[g1][i].to][g[g1][i].rev].cap += kari; return kari; } } } return -1; } public: int max_frow(int s09, int t09){ //sからtへの最大フロー int re = 0; while (1){ bfs(s09); if (level[t09] == -1){ return re; } iter.clear(); iter.assign(g.size(), 0); while (1){ int ka = dfs(s09, t09, -1); if (ka == -1){ break; } else{ re += ka; } } } } void add(int ss21, int gg21, int cost21){ //ssからggにcost分加える ed kari; kari.to = gg21; kari.cap = cost21; kari.rev = g[gg21].size(); g[ss21].push_back(kari); kari.cap = 0; kari.rev = g[ss21].size() - 1; kari.to = ss21; g[gg21].push_back(kari); } vector mat; vector vis; bool b_dfs(int v){ vis[v] = true; for (int i = 0; i < g[v].size(); i++){ int go = g[v][i].to; int w = mat[go]; if (w < 0 || (vis[w] == false && b_dfs(w))){ mat[v] = go; mat[go] = v; return true; } } return false; } int bi(){ int res = 0; vis.assign(g.size(), false); mat.assign(g.size(), -1); for (int i = 0; i < mat.size(); i++){ if (mat[i] < 0){ vis.assign(g.size(), false); if (b_dfs(i)){ res++; } } } return res; } dinic(int n132){ //頂点数 vector vgg; vgg.clear(); g.assign(n132 + 5, vgg); } }; int n; int a[52]; dinic d(300); vector > v; int main(){ scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d", &a[i]); } int base = 1; //base+val int base2 = 52; //base2+i int st = 0; int gol = 120; for (int i = 0; i < n; i++){ d.add(st, base + i, 1); } for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (a[j] == i){ continue; } d.add(base + i, base2 + j, 1); } } for (int i = 0; i < n; i++){ d.add(base2 + i, gol, 1); } int f = d.max_frow(st, gol); if (f != n){ puts("-1"); return 0; } for (int i = 0; i < n; i++){ int ind = base + i; for (int j = 0; j < d.g[ind].size(); j++){ if (d.g[ind][j].cap == 0){ v.push_back(make_pair(d.g[ind][j].to - base2, i)); } } } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++){ printf("%d\n", v[i].second); } return 0; }