#include <cstdint>
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
const int NODE_SIZE = 303030 * 6;
struct euler_tour_tree {
using value_type = long long;
using size_type = std::size_t;
using node_index = std::int_least32_t;
using vertex_index = std::int_least32_t;
struct node;
static struct node n[NODE_SIZE];
static node_index ni;
struct node {
vertex_index s, d;
node_index c[3];
int sz;
int flag;
value_type val;
value_type Sigma;
node(): sz(1) {}
inline node& operator[](size_type d) { return n[c[d]]; }
};
node_index new_edge(int s, int d, bool hi) {
int i = ni++;
int ri = ni++;
n[i].s = n[ri].d = s;
n[i].d = n[ri].s = d;
n[i].sz = n[ri].sz = 0;
n[i].flag = hi;
return i;
}
static void fix(node_index i) {
n[i].sz = (n[i].s == n[i].d) ? 1 : 0;
if(n[i].c[0]) n[i].sz += n[i][0].sz;
if(n[i].c[1]) n[i].sz += n[i][1].sz;
n[i].flag &= 0b0101;
n[i].flag |= n[i].flag << 1;
if(n[i].c[0]) n[i].flag |= n[i][0].flag & 0b1010;
if(n[i].c[1]) n[i].flag |= n[i][1].flag & 0b1010;
n[i].Sigma = n[i].val;
if(n[i].c[0]) n[i].Sigma += n[i][0].Sigma;
if(n[i].c[1]) n[i].Sigma += n[i][1].Sigma;
}
static int child_dir(node_index i) {
if(n[i].c[2]) {
if(n[i][2].c[0] == i) { return 0; }
else if(n[i][2].c[1] == i) { return 1; }
}
return 2;
}
static void rotate(node_index x, size_type dir) {
node_index p = n[x].c[2];
int x_dir = child_dir(x);
node_index y = n[x].c[dir ^ 1];
if(n[y].c[dir]) n[y][dir].c[2] = x;
n[x].c[dir ^ 1] = n[y].c[dir];
n[n[x].c[2] = y].c[dir] = x;
n[y].c[2] = p;
if(x_dir < 2) n[p].c[x_dir] = y;
if(n[x].c[dir ^ 1]) fix(n[x].c[dir ^ 1]);
fix(x);
}
static void splay(node_index i) {
int i_dir;
int j_dir;
while((i_dir = child_dir(i)) < 2) {
node_index j = n[i].c[2];
if((j_dir = child_dir(j)) < 2) {
node_index k = n[j].c[2];
if(i_dir == j_dir) rotate(k, j_dir ^ 1), rotate(j, i_dir ^ 1);
else rotate(j, i_dir ^ 1), rotate(k, j_dir ^ 1);
}
else rotate(j, i_dir ^ 1);
}
fix(i);
}
static node_index merge_back(node_index l, node_index r) {
if(!l) return r;
if(!r) return l;
while(n[l].c[1]) l = n[l].c[1];
splay(l);
n[n[r].c[2] = l].c[1] = r;
fix(l);
return l;
}
static std::pair<node_index, node_index> split(node_index i) {
splay(i);
node_index l = n[i].c[0];
n[i].c[0] = n[l].c[2] = 0;
fix(i);
return { l, i };
}
static void reroot(node_index v) {
auto p = split(v);
merge_back(p.second, p.first);
splay(v);
}
static bool same_root(node_index i, node_index j) {
if(i) splay(i);
if(j) splay(j);
while(n[i].c[2]) i = n[i].c[2];
while(n[j].c[2]) j = n[j].c[2];
return i == j;
}
node_index n_start;
std::unordered_map<long long, node_index> emp;
euler_tour_tree() {}
euler_tour_tree(int N): n_start(ni) {
ni += N;
for(int i = 0; i < N; i++) {
n[i + n_start].s = n[i + n_start].d = i;
}
}
bool edge_exist(vertex_index x, vertex_index y) {
if(x > y) std::swap(x, y);
return emp.count(((long long)x << 32) | (long long)y);
}
void link(vertex_index x, vertex_index y, bool hi) {
if(x > y) std::swap(x, y);
int ei = new_edge(x, y, hi);
assert(!emp.count(((long long)x << 32) | (long long)y));
emp[((long long)x << 32) | (long long)y] = ei;
x += n_start;
y += n_start;
reroot(x);
reroot(y);
n[n[x].c[2] = ei].c[0] = x;
n[n[y].c[2] = ei].c[1] = y;
fix(ei);
merge_back(ei, ei + 1);
}
void cut(vertex_index x, vertex_index y) {
if(x > y) std::swap(x, y);
auto iter = emp.find(((long long)x << 32) | (long long)y);
int ei = iter->second;
int rei = ei + 1;
emp.erase(iter);
auto p = split(ei);
if(p.first && same_root(p.first, rei)) {
auto q = split(rei);
node_index left = q.first;
node_index center = n[q.second].c[1];
node_index right = n[p.second].c[1];
n[center].c[2] = 0;
n[right].c[2] = 0;
merge_back(left, right);
}
else {
splay(ei);
ei = n[ei].c[1];
n[ei].c[2] = 0;
auto q = split(rei);
splay(p.first);
node_index left = p.first;
node_index center = q.first;
node_index right = n[q.second].c[1];
n[right].c[2] = 0;
merge_back(left, right);
}
}
bool same_tree(vertex_index x, vertex_index y) {
return same_root(x + n_start, y + n_start);
}
int tree_size(vertex_index x) {
x += n_start;
splay(x);
return n[x].sz;
}
void subedge_set(vertex_index x, bool val) {
x += n_start;
splay(x);
if(val) n[x].flag |= (0b0100);
else n[x].flag &= ~(0b0100);
fix(x);
}
void add_val(vertex_index x, value_type val) {
x += n_start;
splay(x);
n[x].val += val;
fix(x);
}
value_type tree_sum(vertex_index x) {
x += n_start;
splay(x);
return n[x].Sigma;
}
template<class Func>
void hilevel_edges(vertex_index v, Func f) {
node_index i = v + n_start;
splay(i);
while(i && (n[i].flag & 0b0010)) {
while(1) {
if(n[i].flag & 0b0001) {
f(n[i].s, n[i].d);
splay(i);
n[i].flag &= ~(0b0001);
fix(i);
break;
}
else if(n[i].c[0] && (n[i][0].flag & 0b0010)) i = n[i].c[0];
else i = n[i].c[1];
}
}
}
template<class Func>
int subedges(vertex_index v, Func f) {
node_index i = v + n_start;
splay(i);
while(i && (n[i].flag & 0b1000)) {
while(1) {
if(n[i].flag & 0b0100) {
if(f(n[i].s)) {
return 1;
}
splay(i);
break;
}
else if(n[i].c[0] && (n[i][0].flag & 0b1000)) i = n[i].c[0];
else i = n[i].c[1];
}
}
return 0;
}
void debug_tree(node_index i, std::string indent) {
if(n[i].c[0]) {
debug_tree(n[i].c[0], indent + "l");
}
std::cout << " " << i << " = (" << n[i].s << " " << n[i].d << ")" << " p " << n[i].c[2] << std::endl;
if(n[i].c[1]) {
debug_tree(n[i].c[1], indent + "r");
}
}
};
euler_tour_tree::node_index euler_tour_tree::ni = 1;
euler_tour_tree::node euler_tour_tree::n[NODE_SIZE];
struct online_dynamic_connectivity {
int N;
std::vector<euler_tour_tree> ett;
std::vector<std::vector<std::unordered_set<int>>> E;
online_dynamic_connectivity(int N): N(N) {
ett.emplace_back(N);
E.emplace_back(N);
}
void link(int x, int y) {
if(ett[0].same_tree(x, y)) {
if(E[0][x].size() == 0) ett[0].subedge_set(x, 1);
if(E[0][y].size() == 0) ett[0].subedge_set(y, 1);
E[0][x].insert(y);
E[0][y].insert(x);
}
else {
ett[0].link(x, y, true);
}
}
void replace(int x, int y, int level) {
for(int k = 0; k < level; k++) {
ett[k].cut(x, y);
}
for(int k = level; k --> 0;) {
if(ett[k].tree_size(x) > ett[k].tree_size(y)) std::swap(x, y);
ett[k].hilevel_edges(x, [&](int s, int d) { ett[k + 1].link(s, d, true); });
int res = ett[k].subedges(x, [&](int s) {
for(auto iter = E[k][s].begin(); iter != E[k][s].end(); ) {
int d = *iter;
iter = E[k][s].erase(iter);
E[k][d].erase(s);
if(E[k][s].size() == 0) ett[k].subedge_set(s, 0);
if(E[k][d].size() == 0) ett[k].subedge_set(d, 0);
if(ett[k].same_tree(s, d)) {
if(E[k + 1][s].size() == 0) ett[k + 1].subedge_set(s, 1);
if(E[k + 1][d].size() == 0) ett[k + 1].subedge_set(d, 1);
E[k + 1][s].insert(d);
E[k + 1][d].insert(s);
}
else {
for(int kk = k + 1; kk --> 0;) {
ett[kk].link(s, d, kk == k);
}
return 1;
}
}
return 0;
});
if(res) return;
}
}
void cut(int x, int y) {
for(int k = 0; k < ett.size(); k++) {
if(E[k][x].count(y)) {
E[k][x].erase(y);
E[k][y].erase(x);
if(E[k][x].size() == 0) ett[k].subedge_set(x, 0);
if(E[k][y].size() == 0) ett[k].subedge_set(y, 0);
return;
}
}
for(int k = ett.size(); k --> 0;) {
if(ett[k].edge_exist(x, y)) {
if(k + 1 == ett.size()) {
ett.emplace_back(N);
E.emplace_back(N);
}
replace(x, y, k + 1);
}
}
}
void add_val(int x, long long val) {
ett[0].add_val(x, val);
}
int size(int x) {
return ett[0].tree_size(x);
}
long long sum(int x) {
return ett[0].tree_sum(x);
}
bool same(int x, int y) {
return ett[0].same_tree(x, y);
}
};