#include <bits/stdc++.h>
#include "race.h"
using namespace std;
int best_path(int N, int K, int H[][2], int L[]) {
std::vector<std::list<int>> adj_list(N, std::list<int> ());
std::stack<vector<int>> alt_branch;
int leaf = -1, x, y, parent_x = -1, parent_y = -1, edges = 0, min_path = N+1, sum = 0;
for(int i = 0; i<N; i++) {
adj_list[H[i][0]].push_back(i);
adj_list[H[i][1]].push_back(i);
}
for(int i = 0; i<N and leaf == -1; i++)
if(adj_list[i].size()==1)
leaf = i;
x = leaf;
if(H[adj_list[leaf].front()][1] == x)
y = H[adj_list[leaf].front()][0];
else
y = H[adj_list[leaf].front()][1];
parent_y = adj_list[leaf].front();
sum = L[adj_list[leaf].front()];
edges++;
while(!alt_branch.empty() or adj_list[y].size()!=1) {
if(sum<K) {
if(adj_list[y].size()!=1) {
std::list<int>::iterator i = adj_list[y].begin(), next_y;
if(*i==parent_y)
i++;
next_y = i;
if(adj_list.size()>2)
alt_branch.push({x, y, parent_x, parent_y, sum, edges});
parent_y = *next_y;
if(H[*next_y][1] == y)
y = H[*next_y][0];
else
y = H[*next_y][1];
sum += L[parent_y];
edges++;
}
else {
x = alt_branch.top()[0];
y = alt_branch.top()[1];
parent_x = alt_branch.top()[2];
parent_y = alt_branch.top()[3];
sum = alt_branch.top()[4];
edges = alt_branch.top()[5];
std::list<int>::iterator i = adj_list[y].begin(), next_y;
if(*i==parent_y)
i++;
adj_list[y].erase(i);
i = adj_list[y].begin();
if(*i==parent_y)
i++;
next_y = i;
if(adj_list[y].size()<=2)
alt_branch.pop();
parent_y = *next_y;
if(H[*next_y][1] == y)
y = H[*next_y][0];
else
y = H[*next_y][1];
sum += L[parent_y];
edges++;
}
}
else if(sum>K) {
std::list<int>::iterator i = adj_list[x].begin(), next_x;
if(*i==parent_x)
++i;
next_x = i;
parent_x = *next_x;
if(H[*next_x][1] == x)
x = H[*next_x][0];
else
x = H[*next_x][1];
sum -= L[parent_x];
edges--;
}
else {
min_path = min(min_path, edges);
std::list<int>::iterator i = adj_list[x].begin(), next_x;
if(*i==parent_x)
++i;
next_x = i;
parent_x = *next_x;
if(H[*next_x][1] == x)
x = H[*next_x][0];
else
x = H[*next_x][1];
sum -= L[parent_x];
edges--;
}
}
if(min_path!=N+1)
return min_path;
else
return -1;
}
