#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; template struct hungarian{//n<=m const T inf=numeric_limits::max(); int n, m, max_match, root; T max_cost; vector> cost; vector lx, ly, slack; vector xy, yx, prev, slackx; vector s, t; void update_labels(){ T delta=inf; for(int y=0; y que; for(int x=0; x> &cost):max_match(0), max_cost(0), cost(cost), n(cost.size()), m(cost[0].size()), lx(n, -inf), ly(m), xy(n, -1), yx(m, -1), s(n), t(m), prev(n), slack(m), slackx(m){ for(int x=0; x gn[MAXN], gk[MAXK]; int vn[MAXN], vk[MAXK], ordn[MAXN], ordk[MAXK]; int main() { cin>>k; for(int i=0; i>a>>b; a--; b--; gk[a].push_back(b); gk[b].push_back(a); } cin>>n; for(int i=0; i>a>>b; a--; b--; gn[a].push_back(b); gn[b].push_back(a); } { queue que; que.push(0); bool used[MAXK]={}; used[0]=1; int t=0; while(!que.empty()){ int x=que.front(); que.pop(); ordk[x]=t; vk[t++]=x; for(auto y:gk[x]){ if(used[y]) continue; que.push(y); used[y]=1; } } } const int INF=1e6; int ans=-INF; for(int r=0; r que; que.push(r); bool used[MAXN]={}; used[r]=1; int t=0; while(!que.empty()){ int x=que.front(); que.pop(); ordn[x]=t; vn[t++]=x; for(auto y:gn[x]){ if(used[y]) continue; que.push(y); used[y]=1; } } int dp[MAXN][MAXK]; for(int i=0; i=0; i--){ for(int j=k-1; j>=0; j--){ int x=vn[i], y=vk[j]; for(auto z:gn[x]){ if(ordn[z]0) n1--; if(j>0) k1--; if(k1>n1) continue; vector> cost(k1, vector(n1, -INF)); int i1=0; for(auto z:gn[x]){ if(ordn[z] h(cost); mx=h.max_cost; } if(i==0 && j==0) ans=max(ans, mx); dp[i][j]=max(dp[i][j], mx); } } } if(ans<0){ cout<<-1<