记录编号	247135	评测结果	AAAAAAAAAA
题目名称	共荣圈	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	3.049 s
提交时间	2016-04-08 10:06:45	内存使用	6.29 MiB

//
//  main.cpp
//  血帆海盗
//
//  Created by Qing Liu on 16/4/7.
//  Copyright © 2016年 Qing Liu. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 110000
#define inf 999999999
using namespace std;

struct edge{
    int to,cap,rev;
};
vector<edge>G[maxn];
vector<int>cntt[maxn];
vector<int>duru[maxn];
void addedge(int from,int to,int cap){
    G[from].push_back((edge){to,cap,(int)G[to].size()});
    G[to].push_back((edge){from,0,(int)G[from].size()-1});
}
int level[maxn],ltr[maxn],cnttt[maxn];
void BFS(int s){
    queue<int>que;
    que.push(s);
    memset(level, -1, sizeof(level));
    memset(ltr,0,sizeof(ltr));
    level[s]=0;
    while (!que.empty()) {
        int k=que.front();
        que.pop();
        for (int i=0; i<G[k].size() ;i++) {
            edge &e=G[k][i];
            if (level[e.to]==-1&&e.cap>0) {
                level[e.to]=level[k]+1;
                que.push(e.to);
            }
        }
    }
}
int DFS(int s,int t,int f){
    if(s==t)
        return f;
    for (int &i=ltr[s]; i<G[s].size(); i++) {
        edge &e=G[s][i];
        if (level[e.to]>level[s]&&e.cap>0) {
            int d=DFS(e.to, t, min(e.cap,f));
            if (d>0) {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    };
    return 0;
}
int low[maxn],dcnt=1,prevv[maxn],DFN_CLOCK;
bool ins[maxn];
stack<int>cnt;
void tarjan(int u){
    low[u]=prevv[u]=++DFN_CLOCK;
    ins[u]=1;
    cnt.push(u);
    for (int i=0; i<G[u].size(); i++) {
        edge &e=G[u][i];
        if (e.cap==0) {
            continue;
        }
        if (prevv[e.to]==0) {
            tarjan(e.to);
            low[u]=min(low[u],low[e.to]);
        }
        else if(ins[e.to]){
            low[u]=min(low[u],prevv[e.to]);
        }
    }
    if (low[u]==prevv[u]) {
       // cout<<"case:"<<dcnt<<endl;
        while (1) {
            int k=cnt.top();
            cnt.pop();
            //cntt[dcnt].push_back(k);
            cnttt[k]=dcnt;
         //   cout<<k<<endl;
            ins[k]=0;
            if (k==u) {
                break;
            }
        }
        dcnt++;
    }
}
int max_flow(int s,int t){
    int ans=0;
    BFS(s);
    while (level[t]>0) {
        int f=DFS(s, t, inf);
        while (f>0) {
            ans+=f;
            f=DFS(s, t, inf);
        }
        BFS(s);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    freopen("sphere.in", "r", stdin);
    freopen("sphere.out", "w", stdout);
    int n,m;
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        int from,to;
        cin>>from>>to;
        duru[from].push_back(to);
        addedge(from, to, 1);
    }
    for (int i=1 ;i<=n/2; i++) {
        addedge(0, i, 1);
        addedge(n/2+i, n+1, 1);
    }
    int ans=max_flow(0,n+1);
    for (int i=1; i<=n; i++) {
        if (!prevv[i]) {
            tarjan(i);
        }
    }
    for (int i=n/2+1; i<=n; i++) {
        for (int j=0; j<G[i].size(); j++) {
            edge &e=G[i][j];
            if (e.cap==0||e.to==n+1) {
                continue;
            }
            if (cnttt[e.to]==cnttt[i]) {
                ans--;
            }
        }
    }
    cout<<ans;
    return 0;
}