#define _CRT_SECURE_NO_WARNINGS //#define _GLIBCXX_DEBUG #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; //#define int ll //#define endl "\n" typedef vector vi; typedef vector vvi; typedef pair pii; #define all(c) (c).begin(), (c).end() #define loop(i,a,b) for(ll i=a; i ostream & operator<<(ostream & os, vector const &); template typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple const &){} template typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple const & t){ os << (n==0?"":" ") << get(t); _ot(os, t); } template ostream & operator<<(ostream & os, tuple const & t){ _ot<0>(os, t); return os; } template ostream & operator<<(ostream & os, pair const & p){ return os << "(" << p.first << ", " << p.second << ") "; } template ostream & operator<<(ostream & os, vector const & v){ rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os; } template inline bool chmax(T & x, T const & y){ return x inline bool chmin(T & x, T const & y){ return x>y ? x=y,true : false; } #ifdef DEBUG #define dump(...) (cerr<<#__VA_ARGS__<<" = "<dstへの最大フローを流す */ int const inf = 1e8; struct Dinic { public: typedef int Capacity; struct Edge; int n; vector > g; vector level, iter; struct Edge { int dst; Capacity cap, cap_orig; int revEdge; bool isRev; Edge(int dst, Capacity cap, int revEdge, bool isRev) :dst(dst), cap(cap), cap_orig(cap), revEdge(revEdge), isRev(isRev) {} }; Dinic(int n_) : n(n_), g(vector >(n_)), level(n_), iter(n_) {} void add_edge(int src, int dst, Capacity cap) { g[src].emplace_back(Edge(dst, cap, g[dst].size(), false)); g[dst].emplace_back(Edge(src, 0, g[src].size() - 1, true)); } // src->dstへの最大フローを流す Capacity solve(int src, int dst) { int flow = 0; while(1){ bfs(src); if (level[dst] < 0) return flow; fill(all(iter), 0); int f; while ((f = dfs(src, dst, inf)) > 0) { flow += f; } } } private: void bfs(int s) { level.assign(n,-1); queue q; // 辺の数でみた最短距離 level[s] = 0; q.push(s); while (q.size()) { int v = q.front(); q.pop(); rep(i,g[v].size()){ Edge& e = g[v][i]; if (e.cap > 0 && level[e.dst] < 0) { level[e.dst] = level[v] + 1; q.push(e.dst); } } } } Capacity dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < (int)g[v].size(); i++) { Edge &e = g[v][i]; if (e.cap > 0 && level[v] < level[e.dst]) { int d = dfs(e.dst, t, min(f, e.cap)); if (d > 0) { e.cap -= d; g[e.dst][e.revEdge].cap += d; return d; } } } return 0; } public: // 現在の容量を表示 // フローを流した分だけ破壊的に容量が減る実装になっている void view(){ rep(i,g.size()){ rep(j,g[i].size()){ Edge & e=g[i][j]; if(!e.isRev) printf("%3d->%3d (flow:%d)\n", (int)i, (int)e.dst, (int)e.cap); } } } // 流れたフロー=元々の容量-現在の容量を表示 void view_flow(){ rep(i,g.size()){ rep(j,g[i].size())if(!g[i][j].isRev){ Edge& e = g[i][j]; printf("%3d->%3d (flow:%d)\n", (int)i, (int)e.dst, (int)(e.cap_orig - e.cap)); } } } // 各辺の流量を得たいときはこのようにする(二部マッチングの例) // void doit(){ // for(int i=0;i> N){ Dinic g(N*2+2); int S = N*2, T = N*2+1; rep(i,N){ g.add_edge(S,i,1); g.add_edge(i+N,T,1); int b; cin >> b; rep(j,N)if(j!=b){ g.add_edge(i,j+N,1); } } int f = g.solve(S,T); if(f != N){ puts("-1"); continue; } rep(i,N){ for(auto & e : g.g[i]){ if(e.cap == 0){ cout << e.dst-N << endl; } } } } }