#include "swap.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i = (a); i <= (b); i++) #define repa(i,a,b) for (int i = (a); i >= (b); i--) #define lli long long int #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define MAX 100000 #define u second.first #define v second.second #define w first lli n,m,a,b,c,dis,cont; vector<pair<lli,pair<lli,lli> > > orden; pair<lli,lli> uf[MAX+2]; lli grado[MAX+2],ciclo[MAX+2]; lli sube(lli act) { if (uf[act].first == act) return act; uf[act].first = sube(uf[act].first); return uf[act].first; } void une(lli a, lli b) { uf[b].first = a; uf[a].second = max(uf[a].second, uf[b].second); if (ciclo[b]) ciclo[a] = 1; } void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; m = M; rep(i,0,m-1) orden.push_back({W[i], {U[i]+1, V[i]+1} }); sort(orden.begin(), orden.end()); } int getMinimumFuelCapacity(int X, int Y) { X++; Y++; rep(i,1,n) { uf[i] = {i,0}; grado[i] = 0; ciclo[i] = 0; } for (auto act : orden) { cont++; a = sube(act.u); b = sube(act.v); grado[act.u]++; grado[act.v]++; if (a != b) une(a,b); else ciclo[a] = 1; if (grado[act.u] > uf[a].second) uf[a].second = grado[act.u]; if (grado[act.v] > uf[a].second) uf[a].second = grado[act.v]; a = sube(X); b = sube(Y); if (a == b) { if (uf[a].second > 2 || ciclo[a]) return act.w; } } return -1; }