#include using namespace std; int n; int ans; int len[200005]; vector > D; int sum[200005]; vector need[200005]; vector E[200005]; vector col[200005]; int qeta[400005]; int belone[200005]; int stb[200005]; vector > G[200005]; vector self[200005]; int chk[200005]; vector whe[200005]; bool check(int Q){// int tim=1; while(tim--){ for(int i=1;i<=Q;i++)sum[i]=0,need[i].clear(); for(int i=1;i=0;i--){ bool flg=false;// for(int j=1;j<=Q;j++){ if(sum[j]+D[i].first<=Q){ sum[j]+=D[i].first; flg=true;// need[j].push_back(D[i].second); belone[D[i].second]=j; break; } } if(!flg)break;// if(!i)return true; } } return false; } bool cmp(int a,int b){ return G[a].size()>G[b].size(); } int nxt[200005]; int find(int x){return nxt[x]==x?x:nxt[x]=find(nxt[x]);} int main(){ srand(time(0)); // freopen("city.in","r",stdin); // freopen("city.out","w",stdout); scanf("%d",&n); ans=ceil(sqrt(2*(n-1))); for(int i=1;i<=n;i++){ int k; scanf("%d",&k); len[i]=k; int x; for(int j=1;j<=k;j++){ scanf("%d",&x); whe[i].push_back(x+E[x].size()*n); E[x].push_back(i); } // printf("%lu\n",whe[i].size()); // return 0; ans=max(ans,k); D.push_back(make_pair(k,i)); } sort(D.begin(),D.end()); while(!check(ans))ans++; printf("%d\n",ans); // for(int i=1;i<=n;i++){ // printf("%d ",1); // for(int j=1;j<=len[i];j++)printf("%d ",1); // puts(""); // } for(int i=1;i %d\n",i,u,v,belone[u],belone[v]); G[belone[u]].push_back(make_pair(belone[v],i)); G[belone[v]].push_back(make_pair(belone[u],n+i)); } vector id; for(int i=1;i<=ans;i++)id.push_back(i); int tim=1; while(tim--){ sort(id.begin(),id.end(),cmp); // return 0; //考虑对于每个色块,枚举一下邻接边,然后再随机枚举一个颜色,把他分配给他没出现的地方 //考虑每次选择的颜色,要求出现次数最多好了,然后分配完之后他的位置就可以随便占真是太方便了 //对于相等的就随机选 //不对,这个意思不就是,不管怎么样,都能分配出来,但是还是得按照度数排序,因为极端情况有可能需要用Q+1次,大概是这样 //然后对于每个点其实也不一定要很严格说度数怎么怎么分配,只要一个点往外分配,他自己的位置就一定会空出来,所以就没有问题 //我不应该这么早就定下那些自己指向自己的边应该怎么样选择。 for(int i=0;i D; // for(int j=1;j<=ans;j++){//对于一个颜色,只要对外有一点点就统计好了 // chk[j]=false; // } vector ruozhi; for(int j=0;jn){ if(qeta[id-n]){ ruozhi.push_back(qeta[id-n]); chk[qeta[id-n]]=now; } } else{ if(qeta[id+n]){ ruozhi.push_back(qeta[id+n]); chk[qeta[id+n]]=now; } } } sort(ruozhi.begin(),ruozhi.end()); if(ruozhi.size())D.push_back(ruozhi[0]); for(int i=1;in){ if(qeta[id-n]==ncol){ k=find(k+1); continue; } qeta[id]=ncol; nxt[k]=k+1; break; } else{ if(qeta[id+n]==ncol){ k=find(k+1); continue; } qeta[id]=ncol; nxt[k]=k+1; break; } // if(k+1==G[now].size()){ // puts("error"); // } } } // if(i==0)return 0; D.clear(); int all=2*self[now].size(); for(int j=0;j