#include <vector> #include <iostream> #include "grader.h" using namespace std; const int MAXN = 512; vector<int> g[MAXN + 1], v; int ord[MAXN + 1], ptr; void dfs(int node, int parent) { ord[++ptr] = node; for(int son : g[node]) { if(son != parent) { dfs(son, node); } } } int findEgg(int n, vector<pair<int, int>> edges) { for(int i = 1; i <= n; i++) { g[i].clear(); } for(int i = 0; i < n - 1; i++) { g[edges[i].first].push_back(edges[i].second); g[edges[i].second].push_back(edges[i].first); } ptr = 0; dfs(1, 0); int st = 1, dr = n - 1, answer = n; while(st <= dr) { int mij = (st + dr) / 2; v.clear(); for(int i = 1; i <= mij; i++) { v.push_back(ord[i]); } if(query(v)) { answer = mij; dr = mij - 1; } else { st = mij + 1; } } return ord[answer]; }