#include "friend.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
set<int> v[100010];
vector<bool> vis(100010, 0);
int memo[100010][2];
vector<int> conf;
int findSample(int N, int confidence[], int host[], int protocol[]) {
for (int i = 0; i < N; i++) conf.pb(confidence[i]);
int a[3] = {0, 0, 0};
for (int i = 1; i < N; i++) {
a[protocol[i]]++;
}
if (a[1] == N - 1) {
int tot = 0;
for (int i = 0; i < N; i++) tot += confidence[i];
return tot;
}
if (a[2] == N - 1) {
int tot = 0;
for (int i = 0; i < N; i++) tot = max(confidence[i], tot);
return tot;
}
for (int i = 1; i < N; i++) {
if (protocol[i] == 1 || protocol[i] == 2) {
for (int x : v[host[i]]) {
v[x].insert(i);
v[i].insert(x);
}
}
if (protocol[i] == 0 || protocol[i] == 2) {
v[host[i]].insert(i);
v[i].insert(host[i]);
}
}
int ans = 0;
int tolti = 0;
bool ok = 1;
vector<bool> elim(N + 5, 0);
while (ok) {
vector<int> k;
ok = 0;
// cout << "ok" << endl;
for (int i = 0; i < N; i++) {
if (v[i].size() <= 1 && !elim[i]) {
ans++;
k.pb(i);
ok = 1;
elim[i] = 1;
break;
}
}
for (int x : k) {
if (v[x].size() > 0) {
int u = *(v[x].begin());
// cout << x << endl;
elim[u] = 1;
for (int y : v[u]) {
v[y].erase(u);
}
v[u].clear();
tolti++;
}
}
}
// cout << ans << " " << tolti << endl;
return ans + (N - ans - tolti) / 2;
}
