| #include <iostream> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <cstdlib> |
| #include <vector> |
| #include <set> |
| #include <map> |
| #include <cassert> |
| #include <queue> |
| #include <ctime> |
| #include <string> |
| #include <cstring> |
| #include <random> |
| #define mp make_pair |
| #define pb push_back |
| #define NAME "" |
| #define y1 y1_423 |
| #define list lista |
| using namespace std; |
| typedef long long ll; |
| typedef long double ld; |
| template<typename T> |
| ostream& operator << (ostream& cout, const vector<T> &a) { |
| if ((int)a.size() == 0) { |
| return (cout << "()"); |
| } |
| cout << "(" << a[0]; |
| for (int i = 1; i < (int)a.size(); i++) { |
| cout << "; " << a[i]; |
| } |
| return (cout << ")"); |
| } |
| template<typename T> |
| ostream& operator << (ostream& cout, const set<T> &a) { |
| if ((int)a.size() == 0) { |
| return (cout << "{}"); |
| } |
| auto it = a.begin(); |
| cout << "{" << *it; |
| ++it; |
| for (; it != a.end(); ++it) { |
| cout << "; " << *it; |
| } |
| return (cout << "}"); |
| } |
| template<typename T> |
| ostream& operator << (ostream& cout, const multiset<T> &a) { |
| if ((int)a.size() == 0) { |
| return (cout << "{}"); |
| } |
| auto it = a.begin(); |
| cout << "{" << *it; |
| ++it; |
| for (; it != a.end(); ++it) { |
| cout << "; " << *it; |
| } |
| return (cout << "}"); |
| } |
| template<typename T1, typename T2> |
| ostream& operator << (ostream& cout, const pair<T1, T2> &a) { |
| return cout << "(" << a.first << "; " << a.second << ")"; |
| } |
| random_device gen; |
| mt19937 rnd(gen()); |
| const int nmax = 2000 * 1000; |
| const int inf = 2000 * 1000 * 1000; |
| const ll infl = 1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll; |
| const int mod = 1000 * 1000 * 1000 + 7; |
| const ld pi = acos(-1.0); |
| int top = 1; |
| bool used[nmax]; |
| int answer[nmax]; |
| set<int> now, color[nmax]; |
| vector<int> a[nmax]; |
| void dfs(int v, int p = -1) { |
| used[v] = true; |
| if (p == -1) { |
| for (int u : color[v]) { |
| answer[u] = top++; |
| } |
| top--; |
| } else { |
| now.clear(); |
| int cnt = 1; |
| for (int u : color[v]) { |
| if (answer[u] != 0) { |
| now.insert(answer[u]); |
| } |
| } |
| for (int u : color[v]) { |
| if (answer[u] != 0) continue; |
| while (now.find(cnt) != now.end()) { |
| cnt++; |
| } |
| answer[u] = cnt++; |
| } |
| } |
| for (int u : a[v]) { |
| if (!used[u]) dfs(u, v); |
| } |
| } |
| int n, m, x, y, s; |
| int main() { |
| //freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); |
| //freopen(NAME".in", "r", stdin);freopen(NAME".out", "w", stdout); |
| cin >> n >> m; |
| for (int i = 0; i < n; i++) { |
| scanf("%d", &s); |
| for (int j = 0; j < s; j++) { |
| scanf("%d", &x); |
| x--; |
| color[i].insert(x); |
| } |
| } |
| for (int i = 0; i < n - 1; i++) { |
| scanf("%d%d", &x, &y); |
| x--, y--; |
| a[x].pb(y); |
| a[y].pb(x); |
| } |
| int index = 0; |
| for (int i = 0; i < n; i++) { |
| if (color[index].size() < color[i].size()) { |
| index = i; |
| } |
| } |
| dfs(index); |
printf("%d
", (top == 0 ? 1 : top)); |
| for (int i = 0; i < m; i++) { |
| assert(answer[i] <= top); |
| printf("%d ", (answer[i] == 0 ? 1 : answer[i])); |
| } |
| return 0; |
| } |
Комментарии