#line 1 "playspace/main.cpp" #include #line 2 "library/gandalfr/graph/flow_graph.hpp" #line 7 "library/gandalfr/graph/base_graph.hpp" namespace internal { template struct _base_edge { int v[2]; Weight cost; int id; _base_edge() {} _base_edge(int from, int to, Weight cost, int id) : v{from, to}, cost(cost), id(id) {} // x から見た反対側の端点を返す int opp(int x) { if (x == v[0]) { return v[1]; } else if (x == v[1]) { return v[0]; } else { std::abort(); } } friend std::ostream &operator<<(std::ostream &os, const _base_edge &e) { e.print(os); return os; } protected: virtual void print(std::ostream &os) const = 0; }; } // namespace internal template struct edge : public internal::_base_edge { using internal::_base_edge::_base_edge; edge reverse() const { return {this->v[1], this->v[0], this->cost, this->id}; } protected: void print(std::ostream &os) const override { os << this->v[0] << " " << this->v[1] << " " << this->cost; } }; template <> struct edge : public internal::_base_edge { static inline const int cost = 1; using internal::_base_edge::_base_edge; edge(int _from, int _to, int _id) : _base_edge(_from, _to, 1, _id) {} edge reverse() const { return {v[1], v[0], 1, id}; } protected: void print(std::ostream &os) const override { os << this->v[0] << " " << this->v[1]; } }; template struct flow_edge : public internal::_base_edge { Weight res, cap; flow_edge(int from, int to, Flow res, Flow cap, int id) : internal::_base_edge(from, to, 1, id), res(res), cap(cap) {} flow_edge(int from, int to, Flow res, Flow cap, Weight cost, int id) : internal::_base_edge(from, to, cost, id), res(res), cap(cap) { } flow_edge reverse() const { return {this->v[1], this->v[0], cap - res, cap, this->cost, this->id}; } // x から見た残余 Flow residual(int x) const { if (x == this->v[0]) { return res; } else if (x == this->v[1]) { return cap - res; } else { std::abort(); } } // x から見て残余がゼロか? Flow is_full(int x) const { if (x == this->v[0]) { return res == 0; } else if (x == this->v[1]) { return cap - res == 0; } else { std::abort(); } } // x から流量を d だけ追加 void add_flow(int x, Flow d) { if (x == this->v[0]) { res -= d; } else if (x == this->v[1]) { res += d; } else { std::abort(); } } protected: void print(std::ostream &os) const override { os << this->v[0] << " " << this->v[1] << " " << cap - res << "/" << cap; } }; namespace internal { template class _base_graph { protected: int N; std::vector> G; std::vector> E; public: _base_graph(){}; _base_graph(int n) : N(n), G(n){}; _base_graph(int n, int m) : N(n), G(n) { E.reserve(m); }; /** * @return ノードの数 */ int count_nodes() const { return N; } /** * @return 辺の数 */ int count_edges() const { return E.size(); } /** * @param n ノード番号 * @return ノード n からの隣接頂点のリストの const 参照 */ const std::vector &operator[](int n) const { return G[n]; } /** * @return グラフ全体の辺のポインタのリストの const 参照 */ const std::vector> &edges() const { return E; } void print() const { std::cout << this->N << " " << this->E.size() << std::endl; for (auto &e : this->E) std::cout << *e << std::endl; } }; } // namespace internal #line 4 "library/gandalfr/graph/flow_graph.hpp" template class flow_graph : public internal::_base_graph> { public: using internal::_base_graph>::_base_graph; flow_graph(const flow_graph &other) : flow_graph(other.N) { for (auto &e : other.E) { add_edge(*e); } } /** * @brief ノードの数をn個まで増やす * @param n サイズ * @attention 今のノード数より小さい数を渡したとき、変化なし */ void expand(int n) { if (n <= this->N) return; this->N = n; this->G.resize(n); } /** * @attention 辺の id は保持される */ void add_edge(const flow_edge &e) { this->E.emplace_back(std::make_unique>(e)); this->G[e.v[0]].push_back(this->E.back().get()); this->G[e.v[1]].push_back(this->E.back().get()); } /** * @attention 辺の id は、(現在の辺の本数)番目 が振られる */ void add_edge(int from, int to, Flow capacity) { int id = (int)this->E.size(); flow_edge e(from, to, capacity, capacity, id); this->E.emplace_back(std::make_unique>(e)); this->G[from].push_back(this->E.back().get()); this->G[to].push_back(this->E.back().get()); } Flow Ford_Fulkerson(int s, int t) { static_assert(std::is_integral::value, "Flow must be an integer type"); Flow flow = 0; while (true) { std::vector vis(this->N, false); auto dfs = [&](auto self, int cur, Flow f) -> Flow { if (cur == t) return f; vis[cur] = true; for (auto &e : this->G[cur]) { if (vis[e->opp(cur)] || e->is_full(cur)) continue; Flow tmp = self(self, e->opp(cur), std::min(e->residual(cur), f)); if (tmp > static_cast(0)) { e->add_flow(cur, tmp); return tmp; } } return static_cast(0); }; Flow inc = dfs(dfs, s, std::numeric_limits::max()); if (inc == 0) break; flow += inc; } return flow; } Flow Dinic(int s, int t) { const int invalid = std::numeric_limits::max(); Flow flow = 0; while (true) { std::vector dist(this->N, invalid); dist[s] = 0; std::queue q; q.push(s); while(!q.empty()) { int cur = q.front(); q.pop(); for (auto &e: this->G[cur]) { int to = e->opp(cur); if (dist[to] != invalid || e->is_full(cur)) continue; dist[to] = dist[cur] + 1; q.push(to); } } if (dist[t] == invalid) break; while (true) { auto dfs = [&](auto self, int cur, Flow f) -> Flow { if (cur == s) return f; for (auto &e : this->G[cur]) { int to = e->opp(cur); if (dist[to] != dist[cur] - 1) continue; Flow tmp = self(self, to, std::min(e->residual(to), f)); if (tmp > static_cast(0)) { e->add_flow(to, tmp); return tmp; } } return static_cast(0); }; Flow inc = dfs(dfs, t, std::numeric_limits::max()); if (inc == 0) break; flow += inc; } } return flow; } }; #line 8 "library/gandalfr/other/io_supporter.hpp" template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (int i = 0; i < (int)v.size(); i++) os << v[i] << (i + 1 != (int)v.size() ? " " : ""); return os; } template std::ostream &operator<<(std::ostream &os, const std::set &st) { for (const T &x : st) { std::cout << x << " "; } return os; } template std::ostream &operator<<(std::ostream &os, const std::multiset &st) { for (const T &x : st) { std::cout << x << " "; } return os; } template std::ostream &operator<<(std::ostream &os, const std::deque &dq) { for (const T &x : dq) { std::cout << x << " "; } return os; } template std::ostream &operator<<(std::ostream &os, const std::pair &p) { os << p.first << ' ' << p.second; return os; } template std::ostream &operator<<(std::ostream &os, std::queue &q) { int sz = q.size(); while (--sz) { os << q.front() << ' '; q.push(q.front()); q.pop(); } os << q.front(); q.push(q.front()); q.pop(); return os; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &in : v) is >> in; return is; } template std::istream &operator>>(std::istream &is, std::pair &p) { is >> p.first >> p.second; return is; } #line 4 "playspace/main.cpp" using namespace std; using ll = long long; const int INF = 1001001001; const ll INFLL = 1001001001001001001; const ll MOD = 1000000007; const ll _MOD = 998244353; #define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++) #define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--) #define all(a) (a).begin(),(a).end() #define debug(a) std::cerr << #a << ": " << a << std::endl #define LF cout << endl #ifdef ENABLE_MULTI_FOR #define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it) #endif template inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; } int main(void){ int N; cin >> N; flow_graph G(2 * N + 2, N * N); rep(i,0,N) { G.add_edge(0, i + 1, 1); G.add_edge(i + N + 1, 2 * N + 1, 1); } rep(i,0,N) { int a; cin >> a; rep(j,0,N) { if (j == a) continue; G.add_edge(i + 1, j + N + 1, 1); } } int mch = G.Dinic(0, 2 * N + 1); if (mch != N) { cout << -1 << endl; } else { vector ans(N); rep(i,0,N) { for (auto &e: G[i + 1]) { if (e->is_full(i + 1)) { ans[i] = e->v[1] - N - 1; } } } cout << ans << endl; } }