传送门：点击打开链接
题意：小明在玩一个闯关游戏，共n关，必须按顺序通过，每一关会遇到两个数字（可能一样），他要选择其中一个，如果要选的这个数字是他之前选过的就直接过了这关。
但是他如果在某一关选了数字X，那就不能在经过另一关时选择数字Y当X+Y=2*n-1时，如果在某一关没有数可选的时候游戏结束，问在闯关游戏中小明最多可以通过几关。
思路：2SAT。。每一层，选第1个数字标记为0，选第2个数字标记为1，然后二分答案，建图跑2SAT就行了
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e4 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;struct Edge {int v, nxt;
} E[MX];
int Head[MX][2], erear;
void edge_init() {erear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int z, int u, int v) {E[erear].v = v;E[erear].nxt = Head[u][z];Head[u][z] = erear++;
}
void edge_add(int u, int v) {edge_add(0, u, v);edge_add(1, v, u);
}
int Stack[MX], Belong[MX], vis[MX], ssz, bsz;
void DFS(int u, int s) {vis[u] = 1;if(s) Belong[u] = s;for(int i = Head[u][s > 0]; ~i; i = E[i].nxt) {int v = E[i].v;if(!vis[v]) DFS(v, s);}if(!s) Stack[++ssz] = u;
}
void tarjan(int n) {ssz = bsz = 0;for(int i = 1; i <= n; i++) vis[i] = 0;for(int i = 1; i <= n; i++) {if(!vis[i]) DFS(i, 0);}for(int i = 1; i <= n; i++) vis[i] = 0;for(int i = ssz; i >= 1; i--) {if(!vis[Stack[i]]) DFS(Stack[i], ++bsz);}
}int n, A[MX], B[MX];
vector<PII> S[MX];
bool check(int x) {edge_init();for(int i = 1; i <= 2 * n; i++) S[i].clear();for(int i = 1; i <= x; i++) {for(int k = 0; k <= 1; k++) {int w = 2 * n + 1 - (k ? B[i] : A[i]);for(int j = 0; j < S[w].size(); j++) {PII t = S[w][j];int v = t.first, id = t.second;edge_add(i + (k ? n : 0), v + (id ? 0 : n));edge_add(v + (id ? n : 0), i + (k ? 0 : n));}}S[A[i]].push_back(PII(i, 0));S[B[i]].push_back(PII(i, 1));}tarjan(2 * n);for(int i = 1; i <= n; i++) {if(Belong[i] == Belong[i + n]) return false;}return true;
}
int solve() {int l = 1, r = n, m;while(l <= r) {m = (l + r) >> 1;if(check(m)) l = m + 1;else r = m - 1;}return l - 1;
}
int main() {int T; //FIN;scanf("%d", &T);while(T--) {scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d%d", &A[i], &B[i]);A[i]++; B[i]++;}printf("%d\n", solve());}return 0;
}