//#include "swap.h"
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const int INF = 1e9;
const int BASE = 137;
struct Edge {
int u, v, w;
};
vector<int> weights;
struct Data {
int labu, labv, szu, szv;
bool islineu, islinev;
pair<int,int> lnu, lnv;
};
struct Disjoin_set {
int lab[N], sz[N];
bool isline[N];
pair<int,int> ln[N];
stack<Data> op;
void init (int n) {
rep (i, 1, n) {
lab[i] = i;
sz[i] = 1;
isline[i] = 1;
ln[i] = {i, i};
}
}
int Find (int u) {
return u == lab[u] ? u : Find(lab[u]);
}
void Join (int u, int v){
int uu = u, vv = v;
u = Find(u);
v = Find(v);
op.push({u,v, sz[u], sz[v], isline[u], isline[v], ln[u], ln[v]});
if (u == v) {
isline[u] = 0;
return;
}
if (sz[u] < sz[v]) swap (u, v), swap (uu, vv);
if (min(isline[v], isline[u]) == 0) {
isline[u] = isline[v] = 0;
}
else {
if ((uu != ln[u].fs && uu != ln[u].se) || (vv != ln[v].fs && vv != ln[v].se)) {
isline[u] = isline[v] = 0;
}
else {
static vector<int> vec;
if (ln[u].fs == ln[u].se) {
if (ln[v].fs != vv) ln[u].se = ln[v].fs;
else ln[u].se = ln[v].se;
}
else if (ln[v].fs == ln[v].se) {
if (ln[u].fs != uu) ln[u].se = ln[v].fs;
else ln[u].fs = ln[v].fs;
}
else {
vec = {ln[u].fs, ln[u].se, ln[v].fs, ln[v].se};
ln[u] = {-1, -1};
iter (&id, vec) {
if (id != uu && id != vv) {
if (ln[u].fs == -1) ln[u].fs = id;
else ln[u].se = id;
}
}
}
}
}
lab[v] = u;
sz[u] += sz[v];
}
void roll_back() {
Data &cur = op.top();
op.pop();
int u = cur.labu, v = cur.labv;
lab[u] = cur.labu;
sz[u] = cur.szu;
isline[u] = cur.islineu;
ln[u] = cur.lnu;
lab[v] = cur.labv;
sz[v] = cur.szv;
isline[v] = cur.islinev;
ln[v] = cur.lnv;
}
bool check (int u, int v) {
u = Find(u);
v = Find(v);
if (u != v) return 0;
return isline[u] == 0;
}
}DSU[szBL + 2];
int n, m, Q;
vector<Edge> edges;
///0-idxed
int getBL (int X) { return X / szBL; }
int getLf (int X) { return X * szBL; }
int getRt (int X) { return min(m, (X + 1) * szBL - 1); }
void algo() {
sort (ALL(edges), [] (Edge A, Edge B) { return A.w < B.w; });
rep (bl, 0, getBL(m)) {
if (bl == 0) DSU[bl].init(n);
else {
DSU[bl] = DSU[bl - 1];
stack<Data> ().swap(DSU[bl].op);
}
rep (i, getLf(bl), getRt(bl)) {
DSU[bl].Join(edges[i].u, edges[i].v);
}
}
}
int getMinimumFuelCapacity (int X, int Y) {
++X, ++Y;
reb (bl, getBL(m), 0){
if (DSU[bl].check(X, Y) == 0) {
if (bl == getBL(m)) return -1;
Disjoin_set &cur = DSU[bl];
rep (i, getLf(bl + 1), getRt(bl + 1)) {
cur.Join(edges[i].u, edges[i].v);
if (cur.check(X, Y)) {
reb (j, i, getLf(bl + 1)) cur.roll_back();
return edges[i].w;
}
}
}
else if (bl == 0 && DSU[bl].check(X, Y) == 1) {
Disjoin_set &cur = DSU[bl];
int numdel = 0;
while (cur.check(X, Y)) ++numdel, cur.roll_back();
rep (i, getRt(bl) - numdel + 1, getRt(bl)) {
cur.Join(edges[i].u, edges[i].v);
}
return edges[getRt(bl) - numdel + 1].w;
}
}
return -1;
}
//void init (int _n, int _m, vector<int> _U, vector<int> _V, vector<int> _W) {
void solution() {
// n = _n;
// m = _m;
// rep (i, 0, m - 1) {
// int u = _U[i], v = _V[i], w = _W[i];
// ++u, ++v;
// edges.push_back({u, v, w});
// }
cin >> n >> m;
// n = 1000;
// m = 10000;
rep (i, 1, m) {
int u, v, w;
u = Rand(0, n - 1);
v = Rand(0, n - 1);
// cin >> cauu >> v >> w;
++u,++v;
edges.push_back({u, v, w});
}
algo();
cout << sizeof (DSU) / (1 << 20) <<"\n";
return;
cin >> Q;
rep (i, 1, Q) {
int X, Y;
cin >> X >> Y;
cout << getMinimumFuelCapacity(X, Y) <<"\n";
}
}
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// file ("c");
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
*/
Compilation message
swap.cpp: In function 'void solution()':
swap.cpp:195:24: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
195 | edges.push_back({u, v, w});
| ~~~~~~~~~~~~~~~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccSPsOKM.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvDsGnM.o:swap.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccSPsOKM.o: in function `main':
grader.cpp:(.text.startup+0x1c3): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
