#include "closing.h"
#include <bits/stdc++.h>
using ll = long long;
#define pb push_back
#define all(v) v.begin(), v.end()
const ll N = 3e5 + 10;
const ll INF = 1e18;
using namespace std;
ll n, s1, s2, k;
vector<pair<ll,ll> > g[N];
ll dist[N][2];
void dfs1(ll x,ll p,ll t){
for(auto [u, w] : g[x]){
if(u == p)continue;
dist[u][t] = dist[x][t] + w;
dfs1(u, x, t);
}
}
ll C[2][N];
bool path[N];
vector<ll> curr;
void dfs2(ll x,ll p){
curr.pb(x);
if(x == s2){
for(auto v : curr){
path[v] = true;
}
return;
}
for(auto [u, w] : g[x]){
if(u == p)continue;
dfs2(u, x);
}
curr.pop_back();
}
int max_score(int _n, int _x, int _y, long long _k,vector<int> u, vector<int> v, vector<int> w){
n = _n;
s1 = _x;
s2 = _y;
k = _k;
memset(path, 0, sizeof path);
memset(dist, 0, sizeof dist);
memset(C, 0, sizeof C);
for(int i = 0;i<n;i++)g[i].clear();
for(ll i = 0;i<u.size();i++){
g[u[i]].pb({v[i], w[i]});
g[v[i]].pb({u[i], w[i]});
}
curr.clear();
dfs1(s1, -1, 0);
//assert(0);
dfs1(s2, -1, 1);
for(ll i = 0;i<n;i++){
C[0][i] = min(dist[i][0], dist[i][1]);
C[1][i] = max(dist[i][0], dist[i][1]);
// cout<<i<<": "<<C[0][i]<<" "<<C[1][i]<<endl;
}
vector<ll> vc;
for(ll i = 0;i<n;i++)vc.pb(C[0][i]);
sort(all(vc));
ll sum = 0;
ll cnt = 0;
for(auto u : vc){
sum += u;
if(sum > k)break;
cnt++;
}
ll ans = cnt;
//return cnt;
//vector<ll> dp[2];
vector<ll> dp;
dp.resize(2 * n + 5, INF);
dfs2(s1, -1);
dp[0] = 0;
for(ll i = 0;i<n;i++){
// assert(0);
// cout<<path[i]<<" ";
vector<ll> ndp(2 * n + 5, INF);
// ndp.resize(2 * n + 5, INF);
for(ll j = 0;j<=2 * n;j++){
if(!path[i])ndp[j] = min(ndp[j], dp[j]);
ndp[j+1] = min(ndp[j+1], dp[j] + C[0][i]);
ndp[j+2] = min(ndp[j+2], dp[j] + C[1][i]);
}
swap(dp, ndp);
}
//cout<<endl;
// assert(0);
for(ll i = ans+1;i<dp.size();i++){
// cout<<dp[i]<<endl;
if(dp[i] <= k)ans = i;
}
return ans;
}
