// no proof, please hack me #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template ostream &operator<<(ostream &os, const vector &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } #define COLOR(s) ("\x1b[" s "m") // !!!Modifies ns and edges!!! // n: modified regular bipartite graph // d := max degree = edge chromatic number // iss[c]: edges of color c \in [0, d) // colors[i]: color of edge i struct BipartiteEdgeColoring { int ns[2]; vector> edges; int n; int d; vector colors; vector> iss; BipartiteEdgeColoring() {} BipartiteEdgeColoring(int n0, int n1) : ns{n0, n1}, edges() {} void ae(int u, int v) { assert(0 <= u); assert(u < ns[0]); assert(0 <= v); assert(v < ns[1]); edges.emplace_back(u, v); } void run() { const int m = edges.size(); vector deg[2]; for (int s = 0; s < 2; ++s) deg[s].assign(ns[s], 0); for (const auto &edge : edges) { ++deg[0][edge.first]; ++deg[1][edge.second]; } d = 0; for (int s = 0; s < 2; ++s) for (int u = 0; u < ns[s]; ++u) if (d < deg[s][u]) d = deg[s][u]; // Merge vertices of small degree. for (int s = 0; s < 2; ++s) { priority_queue, vector>, std::greater>> que; par.resize(ns[s]); for (int u = 0; u < ns[s]; ++u) que.emplace(deg[s][u], par[u] = u); for (; ; ) { if (!que.size()) break; const auto p0 = que.top(); que.pop(); if (!que.size()) break; const auto p1 = que.top(); que.pop(); if (p0.first + p1.first > d) break; par[p0.second] = p1.second; que.emplace(p0.first + p1.first, p1.second); } int nn = 0; vector ids(ns[s], -1); for (int u = 0; u < ns[s]; ++u) if (par[u] == u) ids[u] = nn++; ns[s] = nn; if (s == 0) { for (auto &edge : edges) edge.first = ids[root(edge.first)]; } else { for (auto &edge : edges) edge.second = ids[root(edge.second)]; } } // Add edges to make the graph d-regular. n = max(ns[0], ns[1]); for (int s = 0; s < 2; ++s) deg[s].assign(n, 0); for (const auto &edge : edges) { ++deg[0][edge.first]; ++deg[1][edge.second]; } for (int u = 0, v = 0; ; ) { for (; u < n && deg[0][u] >= d; ++u) {} for (; v < n && deg[1][v] >= d; ++v) {} if (u == n && v == n) break; edges.emplace_back(u, v); ++deg[0][u]; ++deg[1][v]; } iss.clear(); vector is(n * d); for (int i = 0; i < n * d; ++i) is[i] = i; rec(is); // Remove added edges. colors.assign(m, -1); for (int k = 0; k < d; ++k) { iss[k].erase(std::lower_bound(iss[k].begin(), iss[k].end(), m), iss[k].end()); for (const int i : iss[k]) colors[i] = k; } } vector par; int root(int u) { return (par[u] == u) ? u : (par[u] = root(par[u])); } // is: k-regular void rec(vector is) { if (!is.size()) return; const int k = is.size() / n; if (k == 1) { std::sort(is.begin(), is.end()); iss.push_back(is); } else if (k % 2 != 0) { if (iss.size()) { is.insert(is.end(), iss.back().begin(), iss.back().end()); iss.pop_back(); rec(is); } else { // Add (2^e - k) bad matchings to find a perfect matching. const int e = (31 - __builtin_clz(k)) + 1; vector ma(n); for (int u = 0; u < n; ++u) ma[u] = ~u; for (; ; ) { auto js = is; for (const int j : ma) for (int l = 0; l < (1 << e) - k; ++l) js.push_back(j); for (int f = e; --f >= 0; ) { const auto jss = euler(js); int numBads[2] = {}; for (int s = 0; s < 2; ++s) for (const int i : jss[s]) if (i < 0) ++numBads[s]; js = jss[(numBads[0] <= numBads[1]) ? 0 : 1]; } ma.swap(js); bool good = true; for (const int j : ma) if (j < 0) { good = false; break; } if (good) break; } std::sort(ma.begin(), ma.end()); iss.push_back(ma); std::sort(is.begin(), is.end()); vector iis; auto it = ma.begin(); for (const int i : is) { for (; it != ma.end() && *it < i; ++it) {} if (!(it != ma.end() && *it == i)) iis.push_back(i); } rec(iis); } } else { const auto jss = euler(is); for (int s = 0; s < 2; ++s) rec(jss[s]); } } // Take Eulerian circuit and take edges alternately. vector> euler(const vector &is) { const int k = is.size() / n; vector pt(n + n); for (int u = 0; u < n + n; ++u) pt[u] = u * k; vector> xvs((n + n) * k); for (int x = 0; x < n * k; ++x) { const int i = is[x]; int u, v; if (i >= 0) { u = edges[i].first; v = n + edges[i].second; } else { u = ~i; v = n + ~i; } xvs[pt[u]++] = std::make_pair(x, v); xvs[pt[v]++] = std::make_pair(x, u); } vector used(n * k, 0); int y = 0; vector> jss(2, vector(n * (k / 2))); vector stack; for (int u0 = 0; u0 < n; ++u0) { for (stack.push_back(u0); stack.size(); ) { const int u = stack.back(); if (pt[u] > u * k) { --pt[u]; const int x = xvs[pt[u]].first; const int v = xvs[pt[u]].second; if (!used[x]) { used[x] = 1; jss[y & 1][y >> 1] = is[x]; ++y; stack.push_back(v); } } else { stack.pop_back(); } } } return jss; } }; //////////////////////////////////////////////////////////////////////////////// vector greedy(const vector °, int m) { const int n = deg.size(); priority_queue> que; for (int i = 0; i < m; ++i) que.emplace(m, i); vector> dus(n); for (int u = 0; u < n; ++u) dus[u] = make_pair(deg[u], u); sort(dus.begin(), dus.end(), greater>{}); vector ret(n, 0); for (const auto &du : dus) { const int c = que.top().first; const int i = que.top().second; que.pop(); if (c < du.first) return {}; que.emplace(c - du.first, i); ret[du.second] = i; } return ret; } int getM(const vector °) { const int n = deg.size(); Int m = 0; for (; !(2 * n - 2 <= m * m); ++m) {} for (int u = 0; u < n; ++u) chmax(m, deg[u]); // girigiri, but too few odd Int sum = 0; for (int u = 0; u < n; ++u) sum += deg[u] / 2; for (; !(sum <= m * (m/2)); ++m) {} return m; } namespace exper { int N; vector deg; Int counter; void test() { // cerr<<"[test] "< (N - u) * d) return; if (u == N) { test(); } else { for (chmin(d, e); d >= 0; --d) { deg[u] = 1 + d; dfs(u + 1, e - d, d); } } } void run() { for (N = 2; ; ++N) { deg.resize(N); counter = 0; dfs(0, N - 2, N - 2); cerr << "PASSED N = " << N << ": counter = " << counter << endl; } } } // exper // DONE N = 83: counter = 18004327 int N; vector C; vector> E; int main() { // exper::run(); for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) { scanf("%d", &N); C.resize(N); E.resize(N); for (int u = 0; u < N; ++u) { scanf("%d", &C[u]); E[u].resize(C[u]); for (int c = 0; c < C[u]; ++c) { scanf("%d", &E[u][c]); --E[u][c]; } } const int M = getM(C); const auto res = greedy(C, M); /* side 0: endpoints of edge side 1: edge from same vertex color */ BipartiteEdgeColoring bec(N - 1, M); for (int u = 0; u < N; ++u) { for (int c = 0; c < C[u]; ++c) { bec.ae(E[u][c], res[u]); } } bec.run(); assert(bec.d <= M); printf("%d\n", M); int id = 0; for (int u = 0; u < N; ++u) { printf("%d", res[u] + 1); for (int c = 0; c < C[u]; ++c) { printf(" %d", bec.colors[id++] + 1); } puts(""); } } #ifndef LOCAL break; #endif } return 0; }