//#include "grader.cpp"
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(n) push_back(n)
vector<vector<int>>edges;
const int N=1e5+5;
int dp[N][2], conf[N], used[N], match[N];
void dfs(int ei,int prev){
dp[ei][1]=conf[ei];
for(auto x : edges[ei]){
if(x == prev) continue;
dfs(x,ei);
dp[ei][0] += dp[x][1];
dp[ei][1] += dp[x][0];
}
dp[ei][1]=max(dp[ei][0],dp[ei][1]);
}
vector<vector<int>>v;
vector<int>l,r;
void add(int a,int b){
v[a].pb(b);
v[b].pb(a);
}
void bpart(int ei,int col=0){
if(col == 0) l.pb(ei);
else r.pb(ei);
used[ei] = true;
for(auto x:edges[ei]){
if(used[x]) continue;
bpart(x, col^1);
}
}
bool check(int ei, int t){
used[ei]=t;
for(auto x : edges[ei]){
if(match[x]==-1||used[match[x]]!=t&&check(match[x],t)){
match[x]=ei;
return true;
}
}
return false;
}
int findSample(int n,int c[],int h[],int p[]){
int ans=0;
for(int i=0;i<n;i++){
conf[i]=c[i];
}
bool e0=1, e1=1, e2=1;
for(int i=1;i<n;i++){
e0=(p[i]!=0?0:e0);
e1=(p[i]!=1?0:e1);
e2=(p[i]!=2?0:e2);
}
if(n<=15){
v.resize(n);
for(int i=1;i<n;i++){
if(p[i]==0) add(h[i],i);
else{
for(auto x:v[h[i]]) add(x,i);
if(p[i]==2) add(h[i],i);
}
}
int mask=1;
while(mask < (1<<n)){
int cost=0;
vector<int> used(n,0);
for(int i=0;i<n;i++){
if(!((1<<i)&mask)) continue;
bool ok=1;
for(auto x:v[i]) if(used[x]) ok=0;
if(ok){
cost+=c[i];
used[i]=1;
}
}
ans=max(ans,cost);
mask++;
}
return ans;
}else if(e1){
for(int i=0;i<n;i++) ans += c[i];
}else if(e2){
for(int i=0;i<n;i++) ans = max(ans, c[i]);
}else if(e0){
for(int i=1;i<n;i++){
edges[i].pb(h[i]);
edges[h[i]].pb(i);
}
dfs(0, 0);
ans = max(dp[0][0], dp[0][1]);
}
else{
v.resize(n);
for(int i=1;i<n;i++){
if(p[i]==0){
add(h[i],i);
edges[h[i]].pb(i);
edges[i].pb(h[i]);
}
else {
for(auto x:v[h[i]]){
add(h[i],i);
edges[x].pb(i);
edges[i].pb(x);
}
if(p[i]==2){
add(h[i],i);
edges[h[i]].pb(i);
edges[i].pb(h[i]);
}
}
}
for(int i=0;i<n;i++){
if(!used[i]) bpart(i,0);
}
for(auto x:l) cout<<x<<" ";
cout<<'\n';
for(auto x:r) cout<<x<<" ";
int s=1001, e=1002;
for(auto x:l) edges[s].pb(x);
for(auto x:r) edges[x].pb(e);
for(int i=0;i<n;i++){
match[i]-1;
}
int time=0;
for(auto ei:l){
time++;
ans += check(ei,time);
}
ans = n-ans;
}
return ans;
}
/*
6
13 3 6 20 10 15
0 0 0 1 2 0
0 0 1 2 1 0
*/
