//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include "grader.h" using namespace std; vector<int>res; vector<vector<int>>nums; map<int,bool>isSeen; void dfs(int num) { isSeen[num]=true,res.push_back(num); for(int i=0;i<nums[num].size();i++) { if(!isSeen[nums[num][i]]) { dfs(nums[num][i]); } } } int findEgg(int n,vector<pair<int,int>>Nums) { int left=0,right=n-1,middle; vector<int>_; res.clear(),nums.clear(),nums.resize(n+1),isSeen.clear(); for(int i=0;i<Nums.size();i++) { nums[Nums[i].first].push_back(Nums[i].second),nums[Nums[i].second].push_back(Nums[i].first); } dfs(1); while(left<=right) { middle=(left+right)/2,_.clear(); for(int i=0;i<=middle;i++) { _.push_back(res[i]); } if(!query(_)) { left=middle+1; } else { right=middle-1; } } return res[left]; }