#include #define LL long long #define LLL __int128 #define uint unsigned #define ldb long double #define uLL unsigned long long using namespace std; const int N=2e5+5; int n,ans,cnt; vectorF[N]; pairE[N]; vector>G[N]; int id[N],A[N],B[N],C[N],sz[N],lst[N]; mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); inline bool solve(){ cnt=0; iota(id+1,id+n+1,1); sort(id+1,id+n+1,[&](int x,int y){ return G[x].size()>G[y].size(); }); int r=n; while(G[id[r]].size()==1)--r; for(int i=1;i<=r;++i){ ++cnt; sz[cnt]=G[id[i]].size(); F[cnt].emplace_back(id[i]); for(;i=ans)++j; F[j].emplace_back(i),++sz[j]; if(j>cnt)++cnt; } if(cnt>ans){ for(int i=1;i<=cnt;++i)F[i].clear(),sz[i]=0; return 0; } for(int i=1;i<=cnt;++i){ vectorS; for(int u:F[i])A[u]=i; for(;;){ S.clear(); for(int j=1;j<=ans;++j)S.emplace_back(j); shuffle(S.begin(),S.end(),rng); int ok=1; for(int u:F[i])for(auto [v,w]:G[u]){ int c=(u==E[w].first?C[w]:B[w]); if(!c)c=lst[v]; if(c==S.back()&&S.size()==1){ok=0;break;} int d=(c==S.back()?S.end()[-2]:S.back()); if(d!=S.back())S.erase(S.end()-2); else S.pop_back(); (u==E[w].first?B[w]:C[w])=d,lst[v]=d; } if(ok)break; for(int u:F[i])for(auto [v,w]:G[u])(u==E[w].first?B[w]:C[w])=0; } } return 1; } void work() { cin>>n,ans=cnt=0; for(int i=1;i>d,G[u].resize(d); for(auto&[v,w]:G[u]) cin>>w,(E[w].first?E[w].second:E[w].first)=u; ans=max(ans,d); } for(int u=1;u<=n;++u)for(auto&[v,w]:G[u]) v=E[w].first^E[w].second^u; while(1ll*ans*ans<(n-1)*2)++ans; if(!solve())++ans,solve(); cout<sync_with_stdio(0); int t; cin>>t; while(t--) work(); return 0; } /* */