#include "highway.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define fr first
#define sc second
using namespace std;
const int N = 90004;
vector <pii> g[N];
int x[N], y[N];
int n, m, a, b;
int S, T;
vector <int> w;
void create(vector <int> &path) {
for (int i = 0; i < m; i++) {
w[i] = 1;
}
for (int edge : path) {
assert(edge < m);
w[edge] = 0;
}
}
long long before = 1e18;
struct Edge {
int id;
int to;
int cost;
Edge (int id_, int to_, int cost_) {
id = id_, to = to_;
}
Edge () {
}
bool operator < (const Edge &other) {
return cost < other.cost;
}
};
void dfs(int v, int par, vector <int> &path) {
vector <Edge> vec; // cost / vertex
for (pii el : g[v]) {
if (el.sc == par) {
continue;
}
path.push_back(el.fr);
create(path);
vec.push_back(Edge(el.fr, el.sc, ask(w)));
path.pop_back();
}
sort (vec.begin(), vec.end());
if (vec.empty() || vec[0].cost == before) {
S = 0, T = v;
} else {
path.push_back(vec[0].id);
before = vec[0].cost;
dfs(vec[0].to, v, path);
}
}
void find_pair(int NN, vector<int> U, vector<int> V, int A, int B) {
n = NN;
m = U.size();
a = A;
b = B;
w.resize(m);
for (int i = 0; i < m; i++) {
x[i] = U[i];
y[i] = V[i];
g[x[i]].push_back({i, y[i]});
g[y[i]].push_back({i, x[i]});
}
vector <int> path = {};
dfs(0, -1, path);
answer(S, T);
}
/*
10
9
4
9
4
1
4 6
9 5
5 0
8 2
1 7
7 4
4 2
2 9
3 9
*/
