#include <bits/stdc++.h>
#include "grader.h"
// #include "grader.cpp"
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define nl '\n'
int findEgg(int n, vector <pair<int, int>> edges) {
vector<set<int>> adj(n);
for(auto &[u, v] : edges) {
u--, v--;
adj[u].emplace(v);
adj[v].emplace(u);
}
vector<int> isl;
auto dfs = [&](auto &&dfs, int v, int p) -> void {
isl.pb(v + 1);
for(auto to : adj[v]) {
if(to == p) continue;
dfs(dfs, to, v);
}
};
auto dfs1 = [&](auto &&dfs, int v, int p, vector<vector<int>> &chd) -> void {
for(auto to : adj[v]) {
if(to == p) continue;
dfs(dfs, to, v, chd);
for(auto i : chd[to]) chd[v].pb(i);
}
};
set<int> vis;
for(int i = 0; i < n; i++) vis.emplace(i);
while(true) {
bool flag = false;
for(auto [u, v] : edges) {
if(vis.find(u) == vis.end()) continue;
if(vis.find(v) == vis.end()) continue;
adj[u].erase(v);
adj[v].erase(u);
dfs(dfs, u, -1);
auto isl1 = isl;
isl.clear();
dfs(dfs, v, -1);
auto isl2 = isl;
isl.clear();
int x = isl1.size(), y = isl2.size();
int cur = x + y;
if((x == cur / 2 && y == (cur + 1) / 2) || (x == (cur + 1) / 2 && y == cur / 2)) {
// cout << "u v " << u + 1 << ' ' << v + 1 << ": ";
if(query(isl1)) {
if(x == 1) {
return isl1[0];
}
for(auto to : isl2) {
to--;
vis.erase(to);
// cout << to + 1 << ' ';
}
} else {
if(y == 1) {
return isl2[0];
}
for(auto to : isl1) {
to--;
vis.erase(to);
// cout << to + 1 << ' ';
}
}
// cout << nl;
flag = true;
break;
}
adj[u].emplace(v);
adj[v].emplace(u);
}
if(!flag) {
for(int r = 0; r < n; r++) {
if(vis.find(r) == vis.end()) continue;
vector <vector<int>> chd(n);
for(int i = 0; i < n; i++) chd[i].pb(i);
dfs1(dfs1, r, -1, chd);
vector<pair<int, int>> tr;
for(auto to : adj[r]) {
tr.emplace_back(chd[to].size(), to);
}
sort(all(tr));
vector<int> isl1;
isl1.pb(r + 1);
for(int i = 0; i < (int)tr.size(); i++) {
int v = tr[i].second;
for(auto to : chd[v]) {
isl1.pb(to + 1);
}
vector<int> isl2;
isl2.pb(r + 1);
for(int j = i + 1; j < (int)tr.size(); j++) {
int v1 = tr[j].second;
for(auto to : chd[v1]) isl2.pb(to + 1);
}
int x = isl1.size(), y = isl2.size();
int cur = x + y;
if((x == cur / 2 && y == (cur + 1) / 2) || (x == (cur + 1) / 2 && y == cur / 2)) {
// cout << "r " << r + 1 << ": ";
if(query(isl1)) {
for(auto to : isl2) {
to--;
// cout << to + 1 << ' ';
if(to == r) continue;
vis.erase(to);
adj[r].erase(to);
}
} else {
for(auto to : isl1) {
to--;
// cout << to + 1 << ' ';
if(to == r) continue;
vis.erase(to);
adj[r].erase(to);
}
}
// cout << nl;
flag = true;
break;
}
}
if(flag) break;
}
}
if(!flag) break;
}
return -1;
}
/**
5
1 2
1 3
2 4
3 5
5
1 2 3 4 5
**/
