#include <iostream>
#include <vector>
#include "grader.h"
#define endl '\n'
using namespace std;
const int MAXN = 1024;
vector < int > e[MAXN];
vector < int > order;
int n;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void dfs(int node, int parent)
{
order.push_back(node);
for(int &nb : e[node])
{
if(nb == parent)
continue;
dfs(nb, node);
//order.push_back(node);
}
}
bool check(int mid)
{
vector < int > q;
q.clear();
for(int i = 0 ; i <= mid ; i++)
{
q.push_back(order[i]);
}
/**
cout << "check --> " << mid <<endl;
for(int i : q)
cout << i << ' ';
cout << endl;
cout << "query_Ans --> " << query(q) <<endl;
**/
int qAns = query(q);
return qAns;
}
int binarySearch()
{
int L = 0, R = order.size() - 1, mid;
while(L < R)
{
mid = (L + R) / 2;
if(check(mid))
R = mid;
else
L = mid + 1;
}
return order[L];
}
void read(int N, vector < pair < int, int > > &bridges)
{
n = N;
for(pair <int , int>& i : bridges)
{
e[i.first].push_back(i.second);
e[i.second].push_back(i.first);
}
}
void clearMemory()
{
for(int i = 0 ; i < MAXN ; i++)
{
e[i].clear();
}
order.clear();
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
//cout << "--------------" << endl;
read(N, bridges);
dfs(1, -1);
/**
cout << "Order: ";
for(int i : order)
cout << i << ' ';
cout << endl;
**/
int ans = binarySearch();
clearMemory();
return ans;
}
/**
13
1 2
1 6
1 5
5 4
3 7
5 3
2 9
2 8
9 11
9 13
10 13
13 12
13
1 2 3 4 5 6 7 8 9 10 11 12 13
**/
