#include #include #include #include #include namespace nachia { struct RegularBipartiteGraph { int n; int k; std::vector> edges; }; RegularBipartiteGraph BipartiteRegularizeEdgeColorEquivalent( int n1, int n2, std::vector> edges ){ std::vector ind1(n1); std::vector ind2(n2); for(auto [u,v] : edges){ ind1[u]++; ind2[v]++; } int k = std::max( *std::max_element(ind1.begin(), ind1.end()), *std::max_element(ind2.begin(), ind2.end())); std::vector map1(n1); std::vector map2(n2); std::vector indx1(std::max(n1, n2)); std::vector indx2(std::max(n1, n2)); indx1[0] += ind1[0]; for(int i=1; i k) map1[i]++; indx1[map1[i]] += ind1[i]; } indx2[0] += ind2[0]; for(int i=1; i k) map2[i]++; indx2[map2[i]] += ind2[i]; } int n = std::max(map1.back() + 1, map2.back() + 1); RegularBipartiteGraph res = { n, k, std::vector>(n*k) }; for(int i=0; i RegularBipartiteEdgeColor(const RegularBipartiteGraph& g){ int n = g.n * 2; std::vector inci(n * g.k); int m = g.n * g.k; std::vector xedge(m); { std::vector head(n); for(int e=0; e flag_e(m); int nx_flag = 0; auto euler_splitting = [&]( std::vector pl, std::vector pr ) -> std::vector { nx_flag++; for(int sp=0; sp& el, std::vector& em, const std::vector& er ) -> void { for(int i=0; i void { std::vector pl(n); std::vector pr(n); for(int i=0; i pm = pr; int md = 1; while(md < n/2*d) md *= 2; int alpha = md / d; while(alpha % 2 == 0){ alpha /= 2; md /= 2; } for(int w=1; w void { if(d <= 1) return; int d2 = d; if(d2 % 2 == 1){ if(s+d2 < g.k) d2++; else{ take_matching(s, d2); d2--; } } std::vector pl(n); std::vector pr(n); for(int i=0; i ans(m); for(int i=0; i BipartiteEdgeColor( int n1, int n2, std::vector> edges ){ int m = edges.size(); auto regularized = BipartiteRegularizeEdgeColorEquivalent(n1, n2, std::move(edges)); auto ans = RegularBipartiteEdgeColor(regularized); ans.resize(m); return ans; } } // namespace nachia using namespace std; #define rep(i,n) for(int i=0; i> bin_packing(vector weight){ int N = weight.size(); int N_original = N; int odd_count = 0; for(int a : weight) if(a % 2 == 1) odd_count += 1; int sum = N * 2 - 2; int Q = *max_element(weight.begin(), weight.end());; while(true){ int req = sum; if(Q % 2 == 1) req += max(0, Q - odd_count); if(req <= (long long)Q * Q) break; Q += 1; } int P = (sum + Q - 1) / Q; if(P < Q) P += 1; while(sum < P*Q){ weight.push_back(1); sum += 1; N += 1; odd_count += 1; } set> even_group, odd_group; rep(i,N) (weight[i] % 2 ? odd_group : even_group).insert({ -weight[i], i }); even_group.insert({ 1, -100 }); odd_group.insert({ 1, -100 }); vector ans(N, -1); auto set_ans = [&](int i, int c){ if(i < 0) exit(1); (weight[i] % 2 ? odd_group : even_group).erase({ -weight[i], i }); ans[i] = c; if(weight[i] % 2 == 1) odd_count -= 1; }; auto extract_max_at = [&](set>& src, int x){ pair res = *src.lower_bound({ -x, -1 }); res.first *= -1; return res; }; auto extract_max = [&](int x){ return max(extract_max_at(even_group, x), extract_max_at(odd_group, x)); }; rep(i,P){ int to_pack = Q; if(Q % 2 == 1){ if(odd_count == P - i){ auto [w,v] = extract_max_at(odd_group, to_pack); set_ans(v, i); to_pack -= w; } while(to_pack > 0){ auto [w,v] = (odd_count == P-i-1) ? extract_max_at(even_group, to_pack) : extract_max(to_pack); set_ans(v, i); to_pack -= w; } } else { while(to_pack > 0){ auto [w,v] = extract_max(to_pack); set_ans(v, i); to_pack -= w; } } } ans.resize(N_original); return {Q,ans}; } void testcase(){ int N; cin >> N; vector> edges(N); rep(i,N){ int c; cin >> c; rep(j,c){ int e; cin >> e; e--; edges[i].push_back(e); } } vector deg(N); rep(i,N) deg[i] = edges[i].size(); auto [Q, vcolor] = bin_packing(deg); vector> bedge; rep(i,N) rep(j,edges[i].size()){ bedge.push_back({ vcolor[i], edges[i][j] }); edges[i][j] = int(bedge.size()) - 1; } auto bcolor = nachia::BipartiteEdgeColor(Q, N-1, bedge); cout << Q << '\n'; rep(i,N){ cout << (vcolor[i] + 1); for(auto e : edges[i]) cout << ' ' << (bcolor[e] + 1); cout << '\n'; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; rep(ti,T) testcase(); return 0; }