Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef pair<int,int>pii;
- #define sf(x) scanf("%d",&x)
- #define sfl(x) scanf("%lld",&x)
- #define lli long long int
- #define ll64 int64_t
- #define pb push_back
- #define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
- #define frr(i,a) for(int i=0;i<a;i++)
- #define frl(i,a) for(lli i=0;i<a;i++)
- const int mx=1004;
- vector<bool>vis;
- vector<int>adj[mx],dis,mst[mx];
- int n;
- void Bfs(int u)
- {
- queue<int>q;
- q.push(u);
- vis[u]=true;
- while(!q.empty())
- {
- int v=q.front();
- //cout<<"v = "<<v<<endl;
- q.pop();
- for(int i=0;i<adj[v].size();i++)
- {
- int x=adj[v][i];
- if(!vis[x])
- {
- //cout<<"x = "<<x<<" ";
- mst[v].pb(x);
- mst[x].pb(v);
- dis[x]=dis[v]+1;
- vis[x]=true;
- q.push(x);
- }
- }
- //cout<<endl;
- }
- return ;
- }
- void bfs(int u)
- {
- for(int i=1;i<=n+2;i++)
- {
- mst[i].clear();
- }
- vis=vector<bool>(n+4,false);
- dis=vector<int>(n+4,0);
- return Bfs(u);
- }
- void Dfs(int u)
- {
- vis[u]=true;
- for(int i=0;i<mst[u].size();i++)
- {
- int x=mst[u][i];
- if(!vis[x])
- {
- dis[x]=dis[u]+1;
- Dfs(x);
- }
- }
- return;
- }
- void dfs(int u)
- {
- /*for(int i=1;i<=n+2;i++)
- {
- for(int j=0;j<mst[i].size();j++)
- {
- cout<<mst[i][j]<<" ";
- }
- cout<<endl;
- }*/
- vis=vector<bool>(n+4,false);
- dis=vector<int>(n+4,0);
- return Dfs(u);
- }
- int main()
- {
- int t;
- sf(t);
- while(t--)
- {
- vector<pii>edge;
- int m,u,v,dm=INT_MAX;
- sf(n);
- for(int j=1;j<=n;j++)
- {
- sf(u);
- sf(m);
- for(int k=0;k<m;k++)
- {
- sf(v);
- adj[u].pb(v);
- edge.pb({u,v});
- }
- }
- for(int i=1;i<=n;i++)
- {
- bfs(i);
- int mx=-1,l;
- for(int j=1;j<=n;j++)
- {
- if(dis[j]>mx)
- {
- mx=dis[j];
- l=j;
- }
- }
- dfs(l);
- mx=-1;
- for(int j=1;j<=n;j++)
- {
- if(dis[j]>mx)
- {
- mx=dis[j];
- }
- }
- dm=min(dm,mx);
- }
- //cout<<"dm = "<<dm<<endl;
- for(int i=0;i<edge.size();i++)
- {
- u=edge[i].first;
- v=edge[i].second;
- //cout<<"u = "<<u<<" v = "<<v<<endl;
- adj[n+2].pb(u);
- adj[n+2].pb(v);
- bfs(n+2);
- int mx=-1,l;
- for(int j=1;j<=n+2;j++)
- {
- if(dis[j]>mx)
- {
- mx=dis[j];
- l=j;
- }
- }
- dfs(l);
- mx=-1;
- for(int j=1;j<=n+2;j++)
- {
- if(dis[j]>mx)
- {
- mx=dis[j];
- }
- }
- adj[n+2].pop_back();
- adj[n+2].pop_back();
- //cout<<u<<" "<<v<<" "<<mx<<endl;
- dm=min(dm,mx-1);
- }
- printf("%d\n",dm);
- for(int i=1;i<=n+2;i++)
- {
- adj[i].clear();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement