#include "sphinx.h" #include<bits/stdc++.h> using namespace std; int n, m; vector<int>x, y; namespace sub12{ vector<int>solve(){ vector<int>ans(n); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ vector<int>c(n, j); c[i] = -1; if(perform_experiment(c) == 1){ ans[i] = j; break; } } } return ans; } } namespace sub3{ bool check_subtask(){ if(m != n - 1){ return false; } for(int i = 0; i < m; i++){ if(y[i] != x[i] + 1){ return false; } } return true; } vector<int>solve(){ vector<int>part(n), ans(n); int N = 0; for(int i = ans[0] = 0; i + 1 < n; i++){ vector<int>c(n, n); c[i] = c[i + 1] = -1; if(perform_experiment(c) > 2 + int(i != 0 && i + 2 != n)){ N++; } part[i + 1] = N; } if(N == 0){ for(int c = 0; c < n; c++){ fill(ans.begin(), ans.end(), -1); ans[0] = c; if(perform_experiment(ans) == 1){ fill(ans.begin(), ans.end(), c); break; } } return ans; } for(int c = 0; c < n; c++){ for(int z = 0; z < 2; z++){ vector<int>color(n, -1); for(int i = 0; i < n; i++){ if((part[i] & 1) == z){ color[i] = c; } } while(true){ int x = perform_experiment(color); if(x == N + 1){ break; } vector<int>cand; for(int i = 0; i < n; i++){ if(color[i] == -1 && (cand.empty() || cand.back() != part[i])){ cand.push_back(part[i]); } } int low = 0, high = int(cand.size()) - 2, pos = -1; while(low <= high){ int mid = (low + high) >> 1; vector<bool>mark(N, false); for(int i = 0; i <= mid; i++){ mark[cand[i]] = true; } vector<int>ncolor = color; for(int i = 0; i < n; i++){ if(mark[part[i]]){ ncolor[i] = n; } } if(perform_experiment(ncolor) == x){ low = (pos = mid) + 1; } else{ high = mid - 1; } } pos++; for(int i = 0; i < n; i++){ if(part[i] == cand[pos]){ ans[i] = c; color[i] = n; } } } } } return ans; } } namespace sub4{ vector<int>solve(){ vector<int>ans(n); for(int i = 0; i < n; i++){ int low = 0, high = n - 2; while(low <= high){ int mid = (low + high) >> 1; vector<int>c(n, n); c[i] = -1; for(int j = 0, cur = 0; j < n && cur <= mid; j++){ if(j != i){ c[j] = cur++; } } if(perform_experiment(c) == mid + 2 + int(mid != n - 2)){ low = ans[i] = mid + 1; } else{ high = mid - 1; } } } return ans; } } namespace sub5{ struct DSU{ vector<int>lab; void init(){ lab.resize(n); iota(lab.begin(), lab.end(), 0); } int find_set(int i){ while(i != lab[i]){ i = lab[i] = lab[lab[i]]; } return i; } bool merge(int i, int j){ if((i = find_set(i)) != (j = find_set(j))){ lab[i] = j; return true; } return false; } }; vector<int>solve(){ vector<vector<int>>g(n); for(int i = 0; i < m; i++){ g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); } DSU d1, d2; d1.init(); d2.init(); function<bool(int, vector<int>)>is_same = [&] (int i, vector<int>J){ vector<int>c(n, n); c[i] = -1; vector<bool>vis(n, false); vis[i] = true; for(int& j : J){ c[j] = -1; vis[j] = true; } int cnt = 1 + J.size(); for(int x = 0; x < n; x++){ if(!vis[x]){ queue<int>q; q.push(x); cnt++; while(!q.empty()){ int u = q.front(); q.pop(); for(int& v : g[u]){ if(!vis[v]){ vis[v] = true; q.push(v); } } } } } return perform_experiment(c) < cnt; }; vector<int>h(n, -1); function<void(int, int)>dfs_1; dfs_1 = [&] (int s, int p){ vector<pair<int, int>>back_edge; for(int& d : g[s]){ if(d != p && h[d] != -1){ back_edge.push_back(make_pair(d1.find_set(d), d)); } } if(!back_edge.empty()){ sort(back_edge.begin(), back_edge.end()); vector<int>cand(1, back_edge[0].second); for(int i = 1; i < back_edge.size(); i++){ if(back_edge[i].first != back_edge[i - 1].first){ cand.push_back(back_edge[i].second); } } while(true){ if(!is_same(s, cand)){ break; } int low = 0, high = int(cand.size()) - 2, pos = -1; while(low <= high){ int mid = (low + high) >> 1; if(!is_same(s, vector<int>(cand.begin(), cand.begin() + mid + 1))){ low = (pos = mid) + 1; } else{ high = mid - 1; } } d1.merge(s, cand[pos + 1]); cand.erase(cand.begin() + pos + 1); } } for(int& d : g[s]){ if(d != p && h[d] == -1){ h[d] = h[s] + 1; if(is_same(s, {d})){ d1.merge(s, d); } dfs_1(d, s); } } }; dfs_1(h[0] = 0, -1); bool is_unique = true; for(int i = 1; i < n; i++){ if(d1.find_set(i) != d1.find_set(0)){ is_unique = false; break; } } if(is_unique){ for(int i = 0; i < n; i++){ vector<int>c(n, -1); c[0] = i; if(perform_experiment(c) == 1){ fill(c.begin(), c.end(), i); return c; } } } vector<vector<int>>tree(n); for(int i = 0; i < m; i++){ if(d2.merge(d1.find_set(x[i]), d1.find_set(y[i]))){ tree[d1.find_set(x[i])].push_back(d1.find_set(y[i])); tree[d1.find_set(y[i])].push_back(d1.find_set(x[i])); } } int root; for(int i = 0; i < n; i++){ if(d1.find_set(i) == i){ root = i; break; } } fill(h.begin(), h.end(), -1); vector<int>ans(n, -1); function<void(int)>dfs_2; dfs_2 = [&] (int s){ for(int& d : tree[s]){ if(h[d] == -1){ h[d] = h[s] + 1; dfs_2(d); } } }; h[root] = 0; dfs_2(root); for(int c = 0; c < n; c++){ for(int z = 0; z < 2; z++){ vector<int>color(n, -1); for(int i = 0; i < n; i++){ if((h[d1.find_set(i)] & 1) == z){ color[i] = c; } } d2.init(); while(true){ int cnt_com = 0; d2.init(); for(int i = 0; i < m; i++){ if(color[x[i]] == color[y[i]] && color[x[i]] != -1){ d2.merge(d1.find_set(x[i]), d1.find_set(y[i])); } } for(int i = 0; i < n; i++){ if(d1.find_set(i) == i && d2.find_set(i) == i){ cnt_com++; } } if(perform_experiment(color) == cnt_com){ break; } vector<int>cand; vector<bool>mark(n, false); for(int i = 0; i < n; i++){ if(color[i] == -1 && ans[i] == -1 && !mark[d1.find_set(i)]){ mark[d1.find_set(i)] = true; cand.push_back(d1.find_set(i)); } } int low = 0, high = int(cand.size()) - 2, pos = high + 1; while(low <= high){ int mid = (low + high) >> 1, expected = 0; fill(mark.begin(), mark.end(), false); for(int i = 0; i <= mid; i++){ mark[cand[i]] = true; } vector<int>ncolor = color; for(int i = 0; i < n; i++){ if(mark[d1.find_set(i)]){ ncolor[i] = n; } } d2.init(); for(int i = 0; i < m; i++){ if(ncolor[x[i]] == ncolor[y[i]] && ncolor[x[i]] != -1){ d2.merge(d1.find_set(x[i]), d1.find_set(y[i])); } } for(int i = 0; i < n; i++){ if(d1.find_set(i) == i && d2.find_set(i) == i){ expected++; } } if(perform_experiment(ncolor) == expected){ high = (pos = mid) - 1; } else{ low = mid + 1; } } for(int i = 0; i < n; i++){ if(d1.find_set(i) == cand[pos]){ ans[i] = c; color[i] = n; } } } } } return ans; } } vector<int>find_colours(int __n, vector<int>__x, vector<int>__y) { swap(x, __x); swap(y, __y); m = x.size(); if((n = __n) <= 50){ return sub12::solve(); } if(sub3::check_subtask()){ return sub3::solve(); } if(m == ((n * (n - 1)) >> 1)){ return sub4::solve(); } return sub5::solve(); }