#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// void dfs2(int u, vector<int>& visited, int team, vector<int>& C, vector<vector<int>>& adj){
// if(team == -2) team = C[u];
// if(visited[u]) return;
// visited[u] = 1;
// for(auto v : adj[u]){
// if(C[v] != team) continue;
// dfs2(u, visited, team, C, adj);
// }
// }
// int amountOfColors(int u, int N, int inc, vector<int> C, vector<vector<int>>& adj){
// C[u] = inc;
// int amount = 0;
// vector<int> visited(N);
// for(int i = 0; i < N; i++){
// if(visited[i]) continue;
// amount++;
// dfs2(u, visited, -2, C, adj);
// }
// return amount;
// }
void color(int u, int parent, int N, vector<int>& found, vector<vector<int>>& adj){
int inc = 0;
while(true){
vector<int> C(N, inc);
C[u] = -1;
C[parent] = inc;
int amount = perform_experiment(C);
if(amount == 1){
found[u] = inc;
break;
}
inc++;
}
return;
}
void dfs(int u, int N, vector<int>& visited, vector<vector<int>>& adj, vector<int>& found){
for(auto v : adj[u]){
if(visited[v]) continue;
color(v, u, N, found, adj);
visited[v] = 1;
dfs(v, N, visited, adj, found);
}
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
vector<int> G(N, 0);
if(N == 2){
for(int i = 0; i < N; i++){
vector<int> E = {-1, i};
int x = perform_experiment(E);
if(x == 1){
G[0] = i;
}
vector<int> F = {i, -1};
x = perform_experiment(F);
if(x == 1){
G[1] = i;
}
}
return G;
}
vector<vector<int>> adj(N);
for(int i = 0; i < X.size(); i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> found(N);
vector<int> visited(N);
dfs(0, N, visited, adj, found);
return found;
}
// #include "grader.cpp"
