module main; // https://kmjp.hatenablog.jp/entry/2015/07/20/1030 より // 2部マッチング import std; // https://ei1333.github.io/library/graph/flow/dinic.hpp より struct Dinic(Flow) { immutable Flow INF; struct Edge { int to; Flow cap; int rev; bool isRev; int idx; } Edge[][] graph; int[] minCost, iter; // コンストラクタ this(int V) { INF = Flow.max; graph.length = V; } void addEdge(int from ,int to, Flow cap, int idx = -1) { graph[from] ~= Edge(to, cap, graph[to].length.to!int, false, idx); graph[to] ~= Edge(from, 0, graph[from].length.to!int - 1, true, idx); } bool buildAugmentPath(int s, int t) { minCost = uninitializedArray!(int[])(graph.length); minCost[] = -1; minCost[s] = 0; auto que = DList!int(s); while (!que.empty && minCost[t] == -1) { int p = que.front; que.removeFront; foreach (e; graph[p]) { if (e.cap <= 0 || minCost[e.to] != -1) continue; minCost[e.to] = minCost[p] + 1; que.insertBack(e.to); } } return minCost[t] != -1; } Flow findMinDistAugmentPath(int idx, in int t, Flow flow) { if (idx == t) return flow; for (int* i = &iter[idx]; *i < graph[idx].length; (*i)++) { Edge* e = &graph[idx][*i]; if (e.cap <= 0 || minCost[idx] >= minCost[e.to]) continue; Flow d = findMinDistAugmentPath(e.to, t, min(flow, e.cap)); if (d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } return 0; } Flow maxFlow(int s, int t) { Flow flow = 0; while (buildAugmentPath(s, t)) { iter = new int[](graph.length); Flow f; while ((f = findMinDistAugmentPath(s, t, INF)) > 0) flow += f; } return flow; } void output() { foreach (i; 0 .. graph.length) { foreach (e; graph[i]) { if (e.isRev) continue; auto revE = graph[e.to][e.rev]; writefln("%d->%d (flow: %d/%d)", i, e.to, revE.cap, e.cap + revE.cap); } } } bool[] minCut(int s) { auto used = new bool[](graph.length); used[s] = true; auto que = DList!int(s); while (!que.empty) { int p = que.front; que.removeFront; foreach (e; graph[p]) { if (e.cap <= 0 || used[e.to]) continue; used[e.to] = true; que.insertBack(e.to); } } return used; } } void main() { // 入力 int N = readln.chomp.to!int; auto mf = Dinic!int(1010); const s = 0, t = 200; auto A = new int[](N); foreach (i; 0 .. N) { mf.addEdge(0, i + 1, 1); mf.addEdge(i + 1 + N, t, 1); A[i] = readln.chomp.to!int; foreach (x; 0 .. N) if (x != A[i]) mf.addEdge(i + 1, N + 1 + x, 1); } // 答えの計算と出力 int f = mf.maxFlow(s, t); if (f < N) { writeln(-1); return; } foreach (i; 0 .. N) { int x; foreach_reverse (r; mf.graph[i + 1]) { if (r.to >= N + 1 && r.to <= 2 * N && r.cap == 0) x = r.to - N - 1; } writeln(x); } }