#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; enum EdgeType { Directed, Undirected }; template struct revCap { static T value(T cap) { (void)cap; return 0; } }; template struct revCap { static T value(T cap) { return cap; } }; template class MF { public: struct Edge { Edge(int t, T c, int r) : to(t), cap(c), rev(r) {} int to; T cap; int rev; }; std::vector> edges_; std::vector iter_; std::vector level_; MF(int v) : edges_(v) {} MF() {} ~MF() {} void init(int v) { edges_.resize(v); } void bfs(int from) { std::fill(level_.begin(), level_.end(), -1); std::queue que; level_[from] = 0; que.push(from); while (!que.empty()) { int v = que.front(); que.pop(); REP(i, edges_[v].size()) { Edge &e = edges_[v][i]; if (e.cap > 0 && level_[e.to] < 0) { level_[e.to] = level_[v]+1; que.push(e.to); } } } return; } T dfs(int v, int to, T f) { if (v == to) return f; for (int &i = iter_[v]; i < (int)edges_[v].size(); ++i) { Edge &e = edges_[v][i]; if (e.cap > 0 && level_[v] < level_[e.to]) { int d = dfs(e.to, to, std::min(f, e.cap)); if (d > 0) { e.cap -= d; edges_[e.to][e.rev].cap += d; return d; } } } return 0; } T max_flow(int from, int to, T inf = std::numeric_limits::max()) { int v = edges_.size(); iter_.resize(v, 0); level_.resize(v, -1); int flow = 0; while (true) { bfs(from); if (level_[to] < 0) return flow; std::fill(iter_.begin(), iter_.end(), 0); int f; while ((f = dfs(from, to, inf))) flow += f; } return -1; } void add(int a, int b, T cap) { edges_[a].emplace_back(b,cap,edges_[b].size()); edges_[b].emplace_back(a,revCap::value(cap),edges_[a].size()-1); } void dump(void) { for (int v = 0; v < (int)edges_.size(); ++v) { cerr<"<>N; vector A(N); REP(i,N) cin>>A[i]; MF mf(2*N+2); int src = 2*N; int sink = src+1; REP(i,N) { mf.add(src,i,1); mf.add(i+N,sink,1); REP(j,N) { if ( j == A[i] ) continue; mf.add(i,j+N,1); } } if ( mf.max_flow(src,sink) < N ) { cout<<-1< 0) continue; cout<<(e.to-N)<solve(); delete obj; return 0; } #endif