#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vf first
#define vs second
int max_score(int n, int x, int y, ll k,vector<int> u, vector<int> v, vector<int> w){
vector<pair<int,ll>> adj[n + 1];
for(int i = 0; i < n-1; i++){
adj[u[i]].pb(mp(v[i] , w[i]));
adj[v[i]].pb(mp(u[i] , w[i]));
}
ll dis[n] , path[n] , dis1[n];
memset(dis,-1,sizeof dis);
memset(path , -1 , sizeof path);
memset(dis1, -1 , sizeof dis1);
queue<int> q;
q.push(x);
dis[x] = 0;
path[x] = 0;
while(q.size()){
int node = q.front();
q.pop();
for(auto i : adj[node]){
if(dis[i.vf] == -1){
dis[i.vf] = dis[node] + i.vs;
path[i.vf] = path[node] + 1;
q.push(i.vf);
}
}
}
bool vis[n];
memset(vis,0,sizeof vis);
vis[y] = 1;
ll cur = y;
vector<int> path_w;
path_w.pb(y);
while(cur != x){
for(auto i : adj[cur]){
if(path[i.vf] == path[cur] - 1){
cur = i.vf;
vis[i.vf] = 1;
path_w.pb(i.vf);
break;
}
}
}
dis1[y] = 0;
q.push(y);
while(q.size()){
int node = q.front();
q.pop();
for(auto i : adj[node]){
if(dis1[i.vf] == -1){
dis1[i.vf] = dis1[node] + i.vs;
path[i.vf] = path[node] + 1;
q.push(i.vf);
}
}
}
/* for(int i = 0; i < n; i++){
cout << dis[i] << ' ' << dis1[i] << '\n';
}*/
int weight[n];
priority_queue<pair<ll,int>> pq;
for(int i = 0; i < n; i++){
if(vis[i] == 0 && dis[i] < dis1[i]){
pq.push(mp(dis[i],i));
}
}
int pos = 0;
while(pq.size()){
//cout << "former " << ' ' << pq.top().vs << '\n';
weight[pos++] = pq.top().vs;
pq.pop();
}
int xx = pos;
while(path_w.size()){
weight[pos++] = path_w.back();
path_w.pop_back();
}
for(int i = 0; i < n; i++){
if(vis[i] == 0 && dis[i] > dis1[i]){
pq.push(mp(dis1[i] , i));
}
}
int yy = pos -1;
vector<int> rev;
while(pq.size()){
rev.pb(pq.top().vs);
pq.pop();
}
while(rev.size()){
//cout << "later " << pq.top().vs << '\n';
weight[pos++] = rev.back();
rev.pop_back();
}
for(int i = 0; i < n; i++){
cout << weight[i] << ' ';
}
cout << '\n';
x = xx;
y = yy;
cur = 0;
int ans = 0;
ll cur_w[n];
for(int i = x; i >= 0; i--){
for(int j = y; j < n; j++){
memset(cur_w,0,sizeof cur_w);
ll rem = k;
ll cur = 0;
for(int tp = x; tp >= i; tp--){
rem -= dis[weight[tp]];
//cout << "dis " << dis[weight[tp]] << ' ';
cur_w[tp] = dis[weight[tp]];
}
cur = 0;
for(int tp = y; tp <= j; tp++){
rem -= dis1[weight[tp]];
//cout << "dis1 " << dis1[weight[tp]] << ' ';
cur_w[tp] = dis1[weight[tp]];
}
//cout << i << ' ' << j << ' ' << rem << endl;
if(rem >= 0){
int res = (x - i) + (j - y) + 2;
// cout << res << ' ';
int left = x + 1 , right = y - 1;
ll cur_l = dis[weight[left]] , cur_r = dis1[weight[right]];
while(rem >= 0 && (left < n || right >= 0)){
//cout << rem << ' ' << left << ' ' << right << endl;
if(right < 0 || (left < n && cur_l - cur_w[left] < cur_r - cur_w[right])){
if(rem - (max(0LL,cur_l - cur_w[left])) >= 0){
rem -= (max(0LL,cur_l - cur_w[left]));
cur_w[left] += (max(0LL,cur_l - cur_w[left]));
res++;
left++;
if(left < n)cur_l = dis[weight[left]];
}
else break;
}
else {
if(rem - max(0LL, cur_r - cur_w[right]) >= 0){
rem -= max(0LL, cur_r - cur_w[right]);
cur_w[right] += max(0LL, cur_r - cur_w[right]);
res++;
right--;
if(right >= 0)cur_r = dis1[weight[right]];
}
else break;
}
}
// cout << i << ' ' << j << ' ' << res << ' ' << rem << ' ' << left << ' ' << right << '\n';
// cout << i << ' ' << j << ' ' << res << ' ' << left << ' ' << right << "\n";
ans = max(ans , res);
}
}
}
return ans;
}
