#include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<std::ostream &operator<<(std::ostream&os,const std::pair&x){return os<<"("<std::ostream &operator<<(std::ostream&os,const std::vector&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<std::ostream &operator<<(std::ostream&os,const std::set&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<std::ostream&operator<<(std::ostream &os,const std::array &arr) {os<<'['<void print(std::ostream&os,const Tup &x,std::index_sequence){(void)(int[]){(os<(x)<<", ",0)...};} templatestd::ostream &operator<<(std::ostream&os,const std::tuple &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence());return os<(x)<<")";} const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m"; #define func_LINE_FILE NORMAL_FAINT<<" in "<"<> es; std::vector lmate, rmate; public: BipartiteMatching() {} BipartiteMatching(int L, int R): lmate(L, -1), rmate(R, -1) {} void add_edge(int l, int r) { es.push_back({l, r}); } void erase_edge(int l, int r) { auto it= std::find(es.begin(), es.end(), std::array{l, r}); if (assert(it != es.end()), es.erase(it); lmate[l] == r) lmate[l]= rmate[r]= -1; } template void build() { const int n= lmate.size(); std::vector g(es.size()), pos(n + 1), rt, pre, que(n); if constexpr (lex) std::sort(es.rbegin(), es.rend()); for (auto [l, r]: es) ++pos[l]; for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i]; for (auto [l, r]: es) g[--pos[l]]= r; for (bool upd= true; upd;) { upd= false, rt.assign(n, -1), pre.assign(n, -1); int t= 0; for (int l= n; l--;) if (lmate[l] == -1) que[t++]= rt[l]= pre[l]= l; for (int i= 0; i < t; ++i) if (int l= que[i]; lmate[rt[l]] == -1) for (int j= pos[l], r, nl; j < pos[l + 1]; ++j) { if (nl= rmate[r= g[j]]; nl == -1) { for (upd= true; r != -1; l= pre[l]) rmate[r]= l, std::swap(lmate[l], r); break; } if (pre[nl] == -1) rt[que[t++]= nl]= rt[pre[nl]= l]; } } if constexpr (lex) { rt.assign(n, 1); for (int v= 0, l, r; v < n; ++v) if (int u= lmate[v]; u != -1) { for (pre.assign(n, lmate[v]= rmate[u]= -1), pre[l= v]= -2, que.assign(pos.begin(), pos.begin() + n);;) { if (que[l] == pos[l + 1]) l= pre[l]; else if (r= g[que[l]++], u= rmate[r]; u == -1) { for (; r != -1; l= pre[l]) rmate[r]= l, std::swap(lmate[l], r); break; } else if (rt[u] && pre[u] == -1) pre[u]= l, l= u; } rt[v]= 0; } } } inline int l_to_r(int l) const { return lmate[l]; } inline int r_to_l(int r) const { return rmate[r]; } std::vector> max_matching() const { std::vector> ret; for (int l= 0, n= lmate.size(); l < n; ++l) if (int r= lmate[l]; r != -1) ret.push_back({l, r}); return ret; } }; class BipartiteGraph { std::vector col, id, pos, g, inv[2]; std::vector> es; BipartiteMatching bm; public: BipartiteGraph(int n): col(n, -1), id(n), pos(n + 1, 0) {} void add_edge(int u, int v) { es.push_back({u, v}); } void build() { const int n= col.size(); g.resize(es.size() * 2); std::vector que(n); for (auto [u, v]: es) ++pos[u], ++pos[v]; for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i]; for (auto [u, v]: es) g[--pos[u]]= v, g[--pos[v]]= u; for (int rt= n; rt--;) if (col[rt] == -1) { id[rt]= inv[0].size(), inv[0].push_back(rt), col[rt]= 0, que[0]= rt; for (int i= 0, t= 1; i < t; ++i) for (int v= que[i], c= col[v], j= pos[v], u; j < pos[v + 1]; ++j) if (assert(col[u= g[j]] != c); col[u] == -1) id[u]= inv[!c].size(), inv[!c].push_back(u), col[u]= !c, que[t++]= u; } bm= BipartiteMatching(inv[0].size(), inv[1].size()); for (auto &[u, v]: es) { if (col[u]) std::swap(u, v); bm.add_edge(id[u], id[v]); } bm.build(); } inline bool color(int v) const { return col[v]; } inline int match(int v) const { int f= col[v], tmp= f ? bm.r_to_l(id[v]) : bm.l_to_r(id[v]); return tmp == -1 ? tmp : inv[!f][tmp]; } std::vector> max_matching() const { auto ret= bm.max_matching(); for (auto &[l, r]: ret) l= inv[0][l], r= inv[1][r]; return ret; } std::vector min_vertex_cover() const { const int n= col.size(); std::vector used(n, -1), que(n), ret; int t= 0; auto bfs= [&](bool f) { for (int i= 0; i < t; ++i) { int v= que[i]; for (int j= pos[v]; j < pos[v + 1]; ++j) { int u= g[j]; if (used[u] != -1) continue; used[u]= f; if (int w= match(u); w != -1 && used[w] == -1) used[que[t++]= w]= f; } } }; for (int v: inv[0]) if (match(v) == -1) used[que[t++]= v]= 0; bfs(0), t= 0; for (int v: inv[1]) if (match(v) == -1) used[que[t++]= v]= 1; bfs(1); for (int v= 0, c; v < n; ++v) { if (c= !col[v]; used[v] == -1) used[que[0]= v]= c, t= 1, bfs(c); if (used[v] ^ !c) ret.push_back(v); } return ret; } }; using namespace std; namespace AOJ3198 { // https://onlinejudge.u-aizu.ac.jp/problems/3198 signed main() { cin.tie(0); ios::sync_with_stdio(0); int N, M; cin >> N >> M; BipartiteMatching bm(N, N); set> pos; for (int i= 0; i < M; ++i) { int a, b; cin >> a >> b, --a, --b; pos.insert({a, b}), bm.add_edge(a, b); } int Q; cin >> Q; while (Q--) { int x, y; cin >> x >> y, --x, --y; if (pos.count({x, y})) pos.erase({x, y}), bm.erase_edge(x, y); else pos.insert({x, y}), bm.add_edge(x, y); bm.build<>(); cout << (bm.max_matching().size() == N ? "Yes" : "No") << '\n'; } return 0; } } namespace AOJ0334 { // https://onlinejudge.u-aizu.ac.jp/problems/0334 signed main() { cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N, --N; BipartiteMatching bm(N, N); for (int i= 0; i < N; ++i) for (int j= 0; j < N; ++j) { int x; cin >> x; if (x) bm.add_edge(j, i); } bm.build<1>(); if (bm.max_matching().size() < N) { cout << "no" << '\n'; } else { cout << "yes" << '\n'; for (int i= 0; i < N; ++i) cout << bm.l_to_r(i) + 1 << '\n'; } return 0; } } namespace AOJ3168 { // https://onlinejudge.u-aizu.ac.jp/problems/3168 signed main() { cin.tie(0); ios::sync_with_stdio(0); int N, M, K; cin >> N >> M >> K; char c[N]; for (int i= 0; i < N; ++i) cin >> c[i]; int dist[N][N]; for (int i= 0; i < N; ++i) fill_n(dist[i], N, K + 1); for (int i= 0; i < N; ++i) dist[i][i]= 0; for (int i= 0; i < M; ++i) { int u, v; cin >> u >> v; --u, --v; dist[u][v]= dist[v][u]= 1; } for (int k= 0; k < N; ++k) for (int i= 0; i < N; ++i) for (int j= 0; j < N; ++j) dist[i][j]= min(dist[i][j], dist[i][k] + dist[k][j]); BipartiteGraph graph(N); for (int i= 0; i < N; ++i) for (int j= 0; j < N; ++j) if (int x= (c[i] - c[j] + 26) % 26; (x == 1 || x == 25) && dist[i][j] <= K) graph.add_edge(i, j); graph.build(); cout << graph.min_vertex_cover().size() << '\n'; return 0; } } namespace atcoder_utpc2013_K { // https://atcoder.jp/contests/utpc2013/tasks/utpc2013_11 signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, m; cin >> n >> m; BipartiteGraph graph(n + n); for (int i= 0; i < m; ++i) { int a, b, f; cin >> a >> b >> f; graph.add_edge(--a, --b); } graph.build(); auto ans= graph.min_vertex_cover(); cout << ans.size() << '\n'; for (int x: ans) cout << x + 1 << '\n'; return 0; } } namespace yukicoder642 { // https://yukicoder.me/problems/642 signed main() { cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; BipartiteGraph graph(N + N); for (int i= 0; i < N; ++i) { int A; cin >> A; for (int j= 0; j < N; ++j) if (j != A) graph.add_edge(i, N + j); } graph.build(); if (graph.max_matching().size() < N) cout << -1 << '\n'; else for (int i= 0; i < N; ++i) cout << graph.match(i) - N << '\n'; return 0; } } signed main() { cin.tie(0); ios::sync_with_stdio(0); // AOJ3198::main(); // AOJ0334::main(); // AOJ3168::main(); // atcoder_utpc2013_K::main(); yukicoder642::main(); return 0; }