//time測定用 //構築未実装 #include #include #include #include #include using namespace std; #define ll long long typedef struct edge3{ ll to,cap,rev; }; typedef struct FordFulkerson{ const ll INF=1000000000000000000; ll MAX_V; vector* G; bool* used; FordFulkerson(){} FordFulkerson(ll max_v){ G=new vector[max_v]; used=new bool[max_v]; MAX_V=max_v; } void add_edge(ll from,ll to,ll cap){ G[from].push_back((edge3){to,cap,G[to].size()}); G[to].push_back((edge3){from,0,G[from].size()-1}); } ll dfs(ll v,ll t,ll f){ if(v==t)return f; used[v]=true; for(int i=0;i0){ ll d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } ll max_flow(ll s,ll t){ ll flow=0; for(;;){ fill(used,used+MAX_V,false); ll f=dfs(s,t,INF); if(f==0)return flow; flow+=f; } return flow; } }; int main(){ ll N,A,B; cin>>N; FordFulkerson F(200002); for(int i=0;i>A>>B; A--;B--; F.add_edge(200000,i,1); F.add_edge(i,100000+A,1); if(A!=B)F.add_edge(i,100000+B,1); F.add_edge(100000+i,200001,1); } //cerr<<"edge added\n"; ll cnt=F.max_flow(200000,200001); //cout<