#include "split.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<utility>
#include<random>
#include<chrono>
using namespace std;
namespace{
vector<int> ord;
vector<int> sz, pa, vis;
vector<vector<int>> graph;
void dfs(int node, int parent){
cout << node << " " << parent << "\n";
sz[node] = 1;
pa[node] = parent;
ord.push_back(node);
vis[node] = 1;
for(auto &x: graph[node]){
//cout << x << " " << vis[x] << " " << parent << "\n";
if(vis[x]) continue;
if(x == parent) continue;
dfs(x, node);
sz[node] += sz[x];
}
}
void dfs_ban(int node, int parent, int ban){
ord.push_back(node);
for(auto &x: graph[node]){
if(x == parent || x == ban) continue;
dfs_ban(x, node, ban);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> ans(n);
sz.resize(n);
graph.resize(n);
pa.resize(n);
vis.resize(n);
for(int i = 0; i < (int)p.size(); i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
dfs(0, 0);
if(a == 1){
//for(auto x: ord) cout << x << ' ';
assert((int)ord.size() == n);
for(int i = 0; i < b; i++) ans[ord[i]] = 2;
for(int i = b; i < b + c; i++) ans[ord[i]] = 3;
ans[ord[n - 1]] = 1;
return ans;
}
int na = 1, nb = 2, nc = 3;
if(a > b){
swap(a, b);
swap(na, nb);
}
if(b > c){
swap(b, c);
swap(nb, nc);
}
if(a > b){
swap(a, b);
swap(na, nb);
}
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);
auto st = clock();
while(float(clock() - st) / CLOCKS_PER_SEC < 1.95){
for(int i = 0; i < n; i++) shuffle(graph[i].begin(), graph[i].end(), mt);
vector<int>().swap(ord);
fill(vis.begin(), vis.end(), 0);
uniform_int_distribution<int> dis(0, n - 1);
int node = dis(mt);
dfs(node, node);
//for(auto &x: ord) cout << x << " ";
vector<int> old = ord, pos(n);
for(int i = 0; i < n; i++) pos[ord[i]] = i;
vector<int>().swap(ord);
for(int i = 0; i < n; i++){
if(sz[i] >= a && n - sz[i] >= b){
dfs_ban(pa[i], pa[i], i);
for(int j = pos[i]; j < pos[i] + a; j++) ans[old[j]] = na;
for(int j = 0; j < b; j++) ans[ord[j]] = nb;
for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
return ans;
}
if(sz[i] >= b && n - sz[i] >= a){
dfs_ban(pa[i], pa[i], i);
for(int j = pos[i]; j < pos[i] + b; j++) ans[old[j]] = nb;
for(int j = 0; j < a; j++) ans[ord[j]] = na;
for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
return ans;
}
}
}
return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run split.cpp grader.cpp
