1 #include<cstdio>  2 #include<vector>  3 #include<cstring>  4 using namespace std;  5   6 const int maxn = 1<<12;  7   8 struct TwoSAT  9 { 10     int n; 11     vector<int> G[maxn*2]; 12     bool mark[maxn*2]; 13     int S[maxn*2], c; 14  15     bool dfs(int x) 16     { 17         if (mark[x^1]) return false; 18         if (mark[x]) return true; 19         mark[x] = true; 20         S[c++] = x; 21         for (int i = 0; i < G[x].size(); i++) 22             if (!dfs(G[x][i])) return false; 23         return true; 24     } 25  26     void init(int n) 27     { 28         this->n = n; 29         for (int i = 0; i < n*2; i++) G[i].clear(); 30         memset(mark, 0, sizeof(mark)); 31     } 32  33     // x = xval or y = yval 34     void add_clause(int x, int xval, int y, int yval) 35     { 36         x = x * 2 + xval; 37         y = y * 2 + yval; 38         G[x^1].push_back(y); 39         G[y^1].push_back(x); 40     } 41  42     bool solve() 43     { 44         for(int i = 0; i < n*2; i += 2) 45             if(!mark[i] && !mark[i+1]) 46             { 47                 c = 0; 48                 if(!dfs(i)) 49                 { 50                     while(c > 0) mark[S[--c]] = false; 51                     if(!dfs(i+1)) return false; 52                 } 53             } 54         return true; 55     } 56 }; 57  58  59 /////////////////////////////////////////////////////////////// 60 #include <iostream> 61 TwoSAT solver; 62 typedef pair<int ,int > CPair; 63 #define K1 first 64 #define K2 second 65 CPair doors[1<<12]; 66 CPair keys[1<<12]; 67 int n; 68  69  70 bool test(int nd) 71 { 72     solver.init(2*n); 73     // 重新构图 74     // 加入钥匙 75     for(int i=0;i<n;i++) 76     { 77         solver.add_clause(keys[i].K1,1,keys[i].K2,1); // 1表示使用key，0表示不使用 78     } 79     // 加入门 80     for(int i=0;i<=nd;i++) 81     { 82         solver.add_clause(doors[i].K1,0,doors[i].K2,0); // 1表示使用key，0表示不使用 83     } 84     return solver.solve(); 85 } 86  87 int main() 88 { 89     #ifndef ONLINE_JUDGE 90     freopen("in.txt","r",stdin); 91     #endif 92  93     int nDoor; 94     while(scanf("%d %d",&n,&nDoor),n+nDoor) 95     { 96         // 添加一对钥匙 97         for(int i=0;i<n;i++) 98         { 99             scanf("%d %d",&keys[i].K1,&keys[i].K2);100         }101 102         // 门103         for(int i=0;i<nDoor;i++)104         {105             scanf("%d %d",&doors[i].K1,&doors[i].K2);106         }107 108         int L=0,R=nDoor-1;109         while(L < R)110         {111             int M = L + (R-L+1)/2;112             if(test(M)) L = M;113             else R = M-1;114         }115         printf("%d\n",L+1);116     }117 118     return 0;119 }