Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- typedef long long LL;
- typedef unsigned long long ULL;
- using namespace std;
- typedef vector<int> vi;
- typedef vector<vi> vii;
- typedef vector<tuple<int,int,int>> vti3;
- #define FOR(i,a,b) for(int i=a;i<b;i++)
- #define pb push_back
- #define ll long long
- #define pob pop_back
- #define si second
- #define fi first
- #define mii map<int,int>
- #define mp make_pair
- #define msi map<string,int>
- #define musi unorderd_map<string,int>
- #define test_n LL N; cin>>N; while(N--)
- #define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
- #define MAXN 100002
- vector<int> adj[MAXN];
- int depth[MAXN];
- vector<int> vertices[MAXN];
- int n;
- inline int dfs(int node){
- int de=0;
- for(auto u:adj[node]){
- de=max(de,dfs(u)+1);
- }
- depth[node]=de;
- vertices[de].pb(node);
- return de;
- }
- struct fhash {
- ll operator() (string x) const { return 69; }
- };
- //===============================//
- unordered_map<string,int,fhash> oup;
- string gof;
- int timer=0;
- //================================//
- inline void mera_util(int node,int k){
- ++timer;
- gof.pb('0'+timer); int myt=timer;
- if(k==0){ gof.pb('0'+myt); return;}
- for(auto u:adj[node]){
- mera_util(u,k-1);
- }
- gof.pb('0'+myt);
- }
- //================================//
- inline bool mera(int k){
- oup.clear();
- vi jog;
- FOR(i,k,n){ jog.pb(i);}
- random_shuffle(jog.begin(),jog.end());
- for(auto i:jog){
- for(auto u:vertices[i]){ timer=0; gof=""; mera_util(u,k); oup[gof]++; if(oup[gof]>1){return true;} }
- }
- return false;
- }
- //================================================//
- int main(){
- fastio;
- srand(unsigned(time(0)));
- test_n{
- cin>>n;
- FOR(i,0,n+1){ adj[i].clear(); vertices[i].clear(); }
- int chi,a;
- FOR(i,1,n+1){
- cin>>chi;
- FOR(j,0,chi){ cin>>a; adj[i].pb(a); }
- }
- dfs(1);
- int ansi=-9;
- int l=0,r=n-1,mid;
- while(l<=r){
- mid=(l+r)/2;
- if(mera(mid)){ ansi=max(ansi,mid); l=mid+1; }
- else{ r=mid-1; }
- }
- cout<<ansi<<"\n";
- }//test_n
- return 0;}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement