#include #include using namespace std; using ll = long long; #define int long long constexpr int N=2e5+10; vectorg[N+1]; bool S1[N],S2[N]; int sz1[N], sz2[N]; int cnt[N]; vector> ops; void dfs_sz(int v, int p=-1){ sz1[v]=S1[v]; sz2[v]=S2[v]; cnt[v]=S1[v]; for(int&u:g[v]){ if(u==p)continue; dfs_sz(u, v); sz1[v]+=sz1[u]; sz2[v]+=sz2[u]; } } void dfs(int v, int p=-1){ // cout<>vec; for(int&u:g[v]){ if(u==p)continue; // sz1[u] ? sz2[u] vec.push_back({(sz1[u]>=sz2[u]), u}); } sort(vec.begin(), vec.end()); reverse(vec.begin(), vec.end()); for(auto&[_, u]:vec){ // cout<<"!!! "<=sz2[u]){ dfs(u, v); } else{ if(cnt[v]0&&p==-1){ cout<<-1<0){ ops.push_back({v, p, cnt[v]}); cnt[p]+=cnt[v]; } } void solve(){ int n; cin>>n; for(int i=1,x,y;i>x>>y; g[x].push_back(y); g[y].push_back(x); } int k; cin>>k; for(int i=0,x;i>x; S1[x]=1; } for(int i=0,x;i>x; S2[x]=1; } dfs_sz(0); dfs(0); assert((int)ops.size()<=10*n); cout<>t; for(int _=1;_<=t;_++){ solve(); } }