#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
vector<int> v;
int N,M;
vector<pair<int,pii>> edges;
void init(int NN, int MM,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
N = NN,M = MM;
for(int i = 0;i<M;i++){
edges.push_back(make_pair(W[i],pii(U[i],V[i])));
}
sort(edges.begin(),edges.end());
return;
}
namespace BIS{
vector<int> paths[mxn];
int dp[mxn];
queue<int> q;
int deg[mxn];
void bfs(int s,int t,int tag){
q.push(s);
dp[s] |= tag;
while(!q.empty()){
auto now = q.front();
q.pop();
if(now == t)continue;
for(auto nxt:paths[now]){
if(dp[nxt]&tag)continue;
dp[nxt]|=tag;
q.push(nxt);
}
}
return;
}
int cnt[mxn];
bool check(int id,int s,int t){
memset(dp,0,sizeof(dp));
memset(deg,0,sizeof(deg));
memset(cnt,0,sizeof(cnt));
for(int i = 0;i<N;i++)paths[i].clear();
for(int i = 0;i<=min(M-1,id);i++){
paths[edges[i].sc.fs].push_back(edges[i].sc.sc);
paths[edges[i].sc.sc].push_back(edges[i].sc.fs);
}
bfs(s,N,1);
if(!dp[t])return false;
for(int i = 0;i<N;i++){
if(dp[i]){
for(auto nxt:paths[i])deg[nxt]++;
}
}
for(int i = 0;i<N;i++){
if(deg[i])cnt[deg[i]]++;
}
if(*max_element(cnt+3,cnt+mxn) == 0&&cnt[1] == 2)return false;
return true;
}
}
int getMinimumFuelCapacity(int X, int Y) {
return -1;
}
