#include using namespace std; #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define memo(a,v) memset(a,v,sizeof(a)) #define CLR(a) memo(a,0) #define SET(a) memo(a,-1) #define pb push_back #define all(a) a.begin(),a.end() #define eps (1e-9) #define inf (1<<30) #define i64 long long #define u64 unsigned i64 #define AIN(a,b,c) assert(a<=b && b<=c) #define MOD 1000000007 #define MAX 605 vector adj[100005],g[1405]; int cap[1405][1405],par[1405],N,n,cnt,P[100005][20],L[100005],D[100005],F[100005],Bx[705],By[705],LCA[705]; void dfs(int x,int p,int lv){ int sz = adj[x].size(); int i, y; L[x] = lv; D[x] = ++cnt; P[x][0] = p; for(i = 0;i= 0; i--) if (L[p] - (1 << i) >= L[q]) p = P[p][i]; if (p == q) return p; for (i = lg; i >= 0; i--) if (P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i]; return P[p][0]; } inline bool IsChild(int u,int v){ if(D[u]<=D[v] && F[v]<=F[u]) return true; return false; } bool intersect(int u1,int v1,int p1,int u2,int v2,int p2){ if(IsChild(p1,p2) && IsChild(p2,u1)) return true; if(IsChild(p1,u2) && IsChild(u2,u1)) return true; if(IsChild(p1,v2) && IsChild(v2,u1)) return true; if(IsChild(p1,p2) && IsChild(p2,v1)) return true; if(IsChild(p1,u2) && IsChild(u2,v1)) return true; if(IsChild(p1,v2) && IsChild(v2,v1)) return true; if(IsChild(p2,p1) && IsChild(p1,u2)) return true; if(IsChild(p2,u1) && IsChild(u1,u2)) return true; if(IsChild(p2,v1) && IsChild(v1,u2)) return true; if(IsChild(p2,p1) && IsChild(p1,v2)) return true; if(IsChild(p2,u1) && IsChild(u1,v2)) return true; if(IsChild(p2,v1) && IsChild(v1,v2)) return true; return false; } void addEdge(int x,int y,int c){ g[x].pb(y); g[y].pb(x); cap[x][y]+=c; } bool bfs(int s,int t){ int i,u,v,sz; queue q; q.push(s); for(i = 0;i0){ par[v] = u; q.push(v); } } } return par[t]!=-1; } int dinic(int s,int t){ int flow = 0,i,u,v; while(bfs(s,t)){ for(i = 0;i