結果

問題 No.529 帰省ラッシュ
ユーザー mdj982mdj982
提出日時 2020-01-08 23:32:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,071 ms / 4,500 ms
コード長 19,608 bytes
コンパイル時間 4,265 ms
コンパイル使用メモリ 273,040 KB
実行使用メモリ 92,848 KB
最終ジャッジ日時 2024-05-02 13:10:45
合計ジャッジ時間 16,021 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 8 ms
6,940 KB
testcase_05 AC 7 ms
6,944 KB
testcase_06 AC 8 ms
6,940 KB
testcase_07 AC 8 ms
6,940 KB
testcase_08 AC 473 ms
39,444 KB
testcase_09 AC 480 ms
44,620 KB
testcase_10 AC 679 ms
69,252 KB
testcase_11 AC 691 ms
70,060 KB
testcase_12 AC 464 ms
39,928 KB
testcase_13 AC 504 ms
92,848 KB
testcase_14 AC 417 ms
36,484 KB
testcase_15 AC 1,066 ms
80,960 KB
testcase_16 AC 1,071 ms
80,956 KB
testcase_17 AC 950 ms
87,632 KB
testcase_18 AC 906 ms
86,476 KB
testcase_19 AC 964 ms
81,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;

const double eps = 1e-7;
#define Loop(i, n) for(int i = 0; i < int(n); i++)
#define Loopll(i, n) for(ll i = 0; i < ll(n); i++)
#define Loop1(i, n) for(int i = 1; i <= int(n); i++)
#define Loopll1(i, n) for(ll i = 1; i <= ll(n); i++)
#define Loopr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = ll(n) - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = int(n); i >= 1; i--)
#define Looprll1(i, n) for(ll i = ll(n); i >= 1; i--)
#define Foreach(buf, container) for(const auto &buf : container)
#define Foreachr(buf, container)  for(const auto &buf : reversed(container))
#define Loopdiag(i, j, h, w, sum) for(int i = ((sum) >= (h) ? (h) - 1 : (sum)), j = (sum) - i; i >= 0 && j < (w); i--, j++)
#define Loopdiagr(i, j, h, w, sum) for(int j = ((sum) >= (w) ? (w) - 1 : (sum)), i = (sum) - j; j >= 0 && i < (h); j--, i++)
#define Loopdiagsym(i, j, h, w, gap) for (int i = ((gap) >= 0 ? (gap) : 0), j = i - (gap); i < (h) && j < (w); i++, j++)
#define Loopdiagsymr(i, j, h, w, gap) for (int i = ((gap) > (h) - (w) - 1 ? (h) - 1 : (w) - 1 + (gap)), j = i - (gap); i >= 0 && j >= 0; i--, j--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(ex_i, vector.size()) { cout << vector[ex_i] << " "; } cout << endl;
#define printmx(matrix) Loop(ex_i, matrix.size()) { Loop(ex_j, matrix[ex_i].size()) { cout << matrix[ex_i][ex_j] << " "; } cout << endl; }
#define quickio() ios::sync_with_stdio(false); cin.tie(0);
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
#define Comp(type_t) bool operator<(const type_t &another) const
#define fst first
#define snd second
#define INF INFINITY
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) { Foreach(x, xs) if (!(x >= 0 && x < t)) return false; return true; }
int ceillog2(ll x) { return int(ceil(log2(x))); }
int floorlog2(ll x) { return int(floor(log2(x))); }
template<class T> T reversed(T container) { reverse(container.begin(), container.end()); return container; }
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (m * m <= x ? 0 : -1); }
ll ceilsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (x <= m * m ? 0 : 1); }
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); }
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }

//========================================================================//

struct tree_t {
	using nodeval_t = priority_queue<ll>;
	using edgeval_t = int;
	int n;           // |V|, index begins with 0
	vector<P> edges; // E
	vector<nodeval_t> vals; // value of nodes
	vector<edgeval_t> costs; // cost, distance, or weight of edges
};


// a should be sorted, return will be the root
template<class val_t, class tree_t>
int make_treap(const vector<val_t> &a, const tree_t &T, int l = 0, int r = -1, int p = -1) {
	if (r == -1) { r = a.size(); T.n = a.size(); }
	if (r - l == 0) return -1;
	int mid = (l + r) / 2;
	if (p != -1) T.edges.push_back({ mid, p });
	make_treap(a, T, l, mid, mid);
	make_treap(a, T, mid + 1, r, mid);
	return mid;
}

#define ANCESTOR
#define HLD
class Tree {
	using nodeval_t = priority_queue<ll>;
	using edgeval_t = int;
private:
	struct node {
		vi childs; int parent = -1;
		int deg = -1; // the number of edges of the path to the root
		int eid = -1; // edge id of the edge connected by its parent and itself
		int subtree_n = 1; // the number of nodes of the partial tree rooted by itself
#ifdef ANCESTOR
		int visited = -1; // time stamp of visiting on DFS, call solve_sprs_ancestors() for activation
		int departed = -1; // time stamp of departure on DFS, call solve_sprs_ancestors() for activation
#endif
#ifdef HLD
		int pid = -1; // path id of heavy light decompotion
		int qid = -1; // id in its path
#endif
		nodeval_t val; // value of the node itself
		edgeval_t cost; // cost of the edge connected by its parent and itself
	};
	struct edgeinfo_t {
		int eid; int to; edgeval_t cost;
	};
	int n;
	nodeval_t init_val;
	static const edgeval_t init_cost = 1;
#ifdef ANCESTOR
	vvi sprs_ancestors; // (1 << j)-th ancestors in each node_id = i
#endif
#ifdef HLD
	vvi hld_paths; // paths
#endif
	void tree_construction(const vector<vector<edgeinfo_t>> &edges) {
		leaves = {};
		queue<int> que;
		que.push(root);
		while (que.size()) {
			int a = que.front(); que.pop();
			deg_order.push_back(a);
			if (a == Tree::root) nodes[a].deg = 0;
			int leaf_flag = true;
			Loop(i, edges[a].size()) {
				int b = edges[a][i].to;
				if (nodes[b].deg != -1) {
					nodes[a].parent = b;
					nodes[a].eid = edges[a][i].eid;
					nodes[a].cost = edges[a][i].cost;
					nodes[a].deg = nodes[b].deg + 1;
				}
				else {
					leaf_flag = false;
					nodes[a].childs.push_back(b);
					que.push(b);
				}
			}
			if (leaf_flag) leaves.push_back(a);
		}
		Loopr(i, n) {
			int a = deg_order[i];
			Loop(j, nodes[a].childs.size()) {
				int b = nodes[a].childs[j];
				nodes[a].subtree_n += nodes[b].subtree_n;
			}
		}
	}
public:
	vector<node> nodes;
	vi deg_order; // node ids, sorted by deg
	vi leaves;
	int root;
public:
	// T should be non-empty tree
	Tree(const tree_t &T, int root) {
		init_val.push(-1);
		this->n = T.n;
		this->root = root;
		nodes.resize(n);
		Loop(i, n) {
			nodes[i].val = (int)(T.vals.size()) > i ? T.vals[i] : init_val;
			nodes[i].cost = init_cost;
		}
		vector<vector<edgeinfo_t>> edges(n);
		Loop(i, n - 1) {
			edges[T.edges[i].fst].push_back({ i, T.edges[i].snd, ((int)(T.costs.size()) > i ? T.costs[i] : init_cost) });
			edges[T.edges[i].snd].push_back({ i, T.edges[i].fst, ((int)(T.costs.size()) > i ? T.costs[i] : init_cost) });
		}
		tree_construction(edges);
		return;
	}
	int solve_diameter() {
		vi d(n, -1);
		queue<int> que;
		d[deg_order[n - 1]] = 0;
		que.push(deg_order[n - 1]);
		while (que.size()) {
			int a = que.front(); que.pop();
			int p = nodes[a].parent;
			if (d[p] == -1) {
				d[p] = d[a] + 1;
				que.push(nodes[a].parent);
			}
			Foreach(b, nodes[a].childs) {
				if (d[b] == -1) {
					d[b] = d[a] + 1;
					que.push(b);
				}
			}
		}
		return *max_element(d.begin(), d.end());
	}
	pair<int, vi> solve_center_of_gravity() {
		pair<int, vi> ret = { INT_MAX,{} };
		vi record(n, 1);
		Foreach(a, deg_order) {
			int x = n - 1, max_x = INT_MIN;
			Foreach(b, nodes[a].childs) {
				max_x = max(max_x, record[b]);
				x -= record[b];
				record[a] += record[b];
			}
			max_x = max(max_x, x);
			if (max_x < ret.fst) ret = { max_x,{ a } };
			else if (max_x == ret.fst) ret.snd.push_back(a);
		}
		sort(ret.snd.begin(), ret.snd.end());
		return ret;
	}
	vi solve_node_inclusion_cnt_in_all_path(bool enable_single_node_path) {
		vi ret(n, 0);
		Loop(i, n) {
			int a = i;
			// desendants to desendants
			Foreach(b, nodes[a].childs) {
				ret[i] += nodes[b].subtree_n * (nodes[a].subtree_n - nodes[b].subtree_n - 1);
			}
			ret[i] /= 2; // because of double counting
			ret[i] += (nodes[a].subtree_n - 1) * (n - nodes[a].subtree_n); // desendants to the others except for itself
			ret[i] += n - 1; // itself to the others
			if (enable_single_node_path) ret[i]++; // itself
		}
		return ret;
	}
	vi solve_edge_inclusion_cnt_in_all_path() {
		vi ret(n - 1, 0);
		Loop(i, n) {
			int eid = nodes[i].eid;
			if (eid < 0) continue;
			ret[eid] = nodes[i].subtree_n * (n - nodes[i].subtree_n); // members in the partial tree to the others
		}
		return ret;
	}
#ifdef ANCESTOR
	void solve_sprs_ancestors() {
		sprs_ancestors.resize(n);
		vector<int> current_ancestors;
		stack<int> stk;
		stk.push(Tree::root);
		int time_stamp = 0;
		while (stk.size()) {
			int a = stk.top(); stk.pop();
			nodes[a].visited = time_stamp++;
			for (int i = 1; i <= (int)(current_ancestors.size()); i *= 2) {
				sprs_ancestors[a].push_back(current_ancestors[current_ancestors.size() - i]);
			}
			if (nodes[a].childs.size()) {
				Loop(i, nodes[a].childs.size()) {
					stk.push(nodes[a].childs[i]);
				}
				current_ancestors.push_back(a);
			}
			else {
				nodes[a].departed = time_stamp++;
				while (current_ancestors.size() && (stk.empty() || nodes[stk.top()].parent != current_ancestors.back())) {
					nodes[current_ancestors.back()].departed = time_stamp++;
					current_ancestors.pop_back();
				}
			}
		}
		return;
	}
	bool is_ancestor(int descendant, int ancestor) {
		return nodes[ancestor].visited < nodes[descendant].visited
			&& nodes[descendant].departed < nodes[ancestor].departed;
	}
	int get_lowest_common_ancestor(int u, int v) {
		if (u == v) return u;
		if (is_ancestor(u, v)) return v;
		if (is_ancestor(v, u)) return u;
		int a = u;
		while (!is_ancestor(v, sprs_ancestors[a][0])) {
			int b = sprs_ancestors[a][0];
			Loop1(i, sprs_ancestors[a].size() - 1) {
				if (is_ancestor(v, sprs_ancestors[a][i])) break;
				else b = sprs_ancestors[a][i - 1];
			}
			a = b;
		}
		return sprs_ancestors[a][0];
	}
	int get_ancestor(int descendant, int k) {
		if (k == 0) return descendant;
		int l = (int)log2(k);
		if (l >= sprs_ancestors[descendant].size()) return -1;
		else return get_ancestor(sprs_ancestors[descendant][l], k - (1 << l));
	}
	// return first value causing "t" in evalfunc that returns descendant->[f,...,f,t,...,t]->root
	// NOTE: if [f,...,f] then return -1
	template<typename bsargv_t>
	int binary_search_upper_ancestor(int descendant, const bsargv_t &bsargv, bool(*evalfunc)(int, const bsargv_t&)) {
		if (evalfunc(descendant, bsargv)) return descendant;
		if (descendant == root) return -1;
		Loop(i, sprs_ancestors[descendant].size()) {
			if (evalfunc(sprs_ancestors[descendant][i], bsargv)) {
				if (i == 0) return binary_search_upper_ancestor(sprs_ancestors[descendant][0], bsargv, evalfunc);
				else return binary_search_upper_ancestor(sprs_ancestors[descendant][i - 1], bsargv, evalfunc);
			}
		}
		return binary_search_upper_ancestor(sprs_ancestors[descendant].back(), bsargv, evalfunc);
	}
	// return last value causing "t" in evalfunc that returns descendant->[t,...,t,f,...,f]->root
	// NOTE: if [f,...,f] then return -1
	template<typename bsargv_t>
	int binary_search_lower_ancestor(int descendant, const bsargv_t &bsargv, bool(*evalfunc)(int, const bsargv_t&)) {
		if (!evalfunc(descendant, bsargv)) return -1;
		if (descendant == root) return root;
		Loop(i, sprs_ancestors[descendant].size()) {
			if (!evalfunc(sprs_ancestors[descendant][i], bsargv)) {
				if (i == 0) return descendant;
				else return binary_search_lower_ancestor(sprs_ancestors[descendant][i - 1], bsargv, evalfunc);
			}
		}
		return binary_search_lower_ancestor(sprs_ancestors[descendant].back(), bsargv, evalfunc);
	}
	// static bool evalfunc(int id, bsargv_t bsargv);
#endif
#ifdef HLD
	void solve_hld() {
		Foreach(a, deg_order) {
			if (nodes[a].pid == -1) {
				nodes[a].pid = int(hld_paths.size());
				nodes[a].qid = 0;
				hld_paths.push_back({ a });
			}
			int max_id = -1;
			int max_subtree_n = 0;
			Foreach(b, nodes[a].childs) {
				if (nodes[b].subtree_n > max_subtree_n) {
					max_id = b;
					max_subtree_n = nodes[b].subtree_n;
				}
			}
			if (max_id == -1) continue;
			nodes[max_id].pid = nodes[a].pid;
			nodes[max_id].qid = nodes[a].qid + 1;
			hld_paths[nodes[a].pid].push_back(max_id);
		}
	}
	struct pathinfo_t {
		int id;
		int l, r; // [l, r)
	};
	// return all node ids in the single path
	vector<int> get_ids_in_path(const pathinfo_t &pathinfo) {
		vi ret(pathinfo.r - pathinfo.l);
		Loop(i, ret.size()) {
			ret[i] = hld_paths[pathinfo.id][pathinfo.l + i];
		}
		return ret;
	}
	// if weight is for each node, include_lca = true
	// if weight is for each edge, include_lca = false
	vector<pathinfo_t> get_path_in_hld(int u, int v, bool include_lca) {
		vector<pathinfo_t> ret;
		int w = get_lowest_common_ancestor(u, v);
		Foreach(x, vector<int>({ u, v })) {
			int a = x;
			while (a != w) {
				if (nodes[a].pid != nodes[w].pid) {
					ret.push_back({ nodes[a].pid, 0, nodes[a].qid + 1 });
					a = nodes[hld_paths[nodes[a].pid][0]].parent;
				}
				else {
					ret.push_back({ nodes[a].pid, nodes[w].qid + 1, nodes[a].qid + 1 });
					a = w;
				}
			}
		}
		if (include_lca) {
			Loop(i, ret.size()) {
				if (nodes[w].pid == ret[i].id) {
					ret[i].l -= 1;
					include_lca = false;
				}
			}
		}
		if (include_lca) {
			ret.push_back({ nodes[w].pid, nodes[w].qid, nodes[w].qid + 1 });
		}
		return ret;
	}
	vi get_hld_path_sizes() {
		vi ret(hld_paths.size());
		Loop(i, hld_paths.size()) {
			ret[i] = int(hld_paths[i].size());
		}
		return ret;
	}
	int get_hld_path_size(int pid) {
		return int(hld_paths[pid].size());
	}
#endif
};

class SegTreeMax {
	using val_t = ll;
private:
	struct segval_t {
		bool enable;
		val_t upd, add, max;
	};
	int n, N; // n is the original size, while N is the extended size
	int base;
	vector<segval_t> nodes;
	vi idl, idr, cover_size;
	void merge(int id) {
		nodes[id].max = max(nodes[idl[id]].max + nodes[idl[id]].add,
			nodes[idr[id]].max + nodes[idr[id]].add);
	}
	void lazy(int id) {
		if (id >= base) return;
		if (nodes[id].enable) {
			val_t upd = nodes[id].upd + nodes[id].add;
			nodes[idl[id]] = { true, upd, 0, upd };
			nodes[idr[id]] = { true, upd, 0, upd };
			nodes[id] = { false, 0, 0, upd };
		}
		else {
			nodes[idl[id]].add += nodes[id].add;
			nodes[idr[id]].add += nodes[id].add;
			nodes[id].add = 0;
			merge(id);
		}
	}
	enum change_t {
		UPD, ADD
	};
	void change_rec(int s, int t, int l, int r, int id, val_t x, change_t op) {
		if (s == l && t == r) {
			if (op == UPD) nodes[id] = { true, x, 0, x };
			else if (op == ADD) nodes[id].add += x;
		}
		else {
			lazy(id);
			int m = (l + r) >> 1;
			if (s < m && m < t) {
				change_rec(s, m, l, m, idl[id], x, op);
				change_rec(m, t, m, r, idr[id], x, op);
			}
			else if (s < m) {
				change_rec(s, t, l, m, idl[id], x, op);
			}
			else if (m < t) {
				change_rec(s, t, m, r, idr[id], x, op);
			}
			merge(id);
		}
	}
	val_t solve_rec(int s, int t, int l, int r, int id) {
		val_t v = 0;
		if (s == l && t == r) {
			v = nodes[id].max;
		}
		else {
			lazy(id);
			int m = (l + r) >> 1;
			if (s < m && m < t) {
				val_t v0 = solve_rec(s, m, l, m, idl[id]);
				val_t v1 = solve_rec(m, t, m, r, idr[id]);
				v = max(v0, v1);
			}
			else if (s < m) {
				v = solve_rec(s, t, l, m, idl[id]);
			}
			else if (m < t) {
				v = solve_rec(s, t, m, r, idr[id]);
			}
		}
		v += nodes[id].add;
		return v;
	}
	void common_init() {
		idl.resize(base + N, -1);
		idr.resize(base + N, -1);
		Loop(i, base) {
			idl[i] = (i << 1) + 1;
			idr[i] = (i << 1) + 2;
		}
		cover_size.resize(base + N);
		Loop(i, n) {
			cover_size[base + i] = 1;
		}
		Loopr(i, base) {
			cover_size[i] = cover_size[idl[i]] + cover_size[idr[i]];
		}
	}
public:
	SegTreeMax(int n, val_t init = LLONG_MIN) {
		this->n = n;
		N = 1 << ceillog2(n);
		base = N - 1;
		nodes = vector<segval_t>(base + N, { false, 0, 0, LLONG_MIN });
		common_init();
		upd(0, n, init);
	}
	SegTreeMax(const vector<val_t> &a) {
		this->n = a.size();
		N = 1 << ceillog2(n);
		base = N - 1;
		nodes = vector<segval_t>(base + N, { false, 0, 0, LLONG_MIN });
		common_init();
		Loop(i, n) {
			nodes[base + i] = { true, a[i], 0, a[i] };
		}
		Loopr(i, base) {
			merge(i);
		}
	}
	void upd(int s, int t, val_t x) {
		if (s >= t) return;
		change_rec(s, t, 0, N, 0, x, UPD);
	}
	void add(int s, int t, val_t x) {
		if (s >= t) return;
		change_rec(s, t, 0, N, 0, x, ADD);
	}
	val_t maxof(int s, int t) {
		if (s >= t) return LLONG_MIN;
		return solve_rec(s, t, 0, N, 0);
	}
};

class Finding_Bridges {
private:
	struct node {
		int id; bool done; vi to; int from; int pre; int low;
	};
	vector<node> nodes;
	int n, m;
	int ord;
	vector<P> result;
	void lowlink_dfs(int a) {
		nodes[a].done = true;
		nodes[a].pre = nodes[a].low = ord;
		ord++;
		Loop(i, nodes[a].to.size()) {
			int b = nodes[a].to[i];
			if (b == nodes[a].from) continue;
			if (!nodes[b].done) {
				nodes[b].from = a;
				lowlink_dfs(b);
				nodes[a].low = min(nodes[a].low, nodes[b].low);
				if (nodes[a].pre < nodes[b].low) {
					if (a < b) result.push_back({ a,b });
					else result.push_back({ b,a });
				}
			}
			else {
				nodes[a].low = min(nodes[a].low, nodes[b].pre);
			}
		}
		return;
	}
public:
	Finding_Bridges(const vvi &lst) {
		n = lst.size();
		nodes.resize(n);
		Loop(i, n) nodes[i] = { i, false,{}, -1, -1, -1 };
		Loop(i, n) {
			Foreach(j, lst[i]) {
				nodes[i].to.push_back(j);
			}
		}
		ord = 0;
		Loop(i, nodes.size()) {
			if (!nodes[i].done) lowlink_dfs(i);
		}
		sort(result.begin(), result.end());
	}
	vector<P> get_bridges() {
		return result;
	}
};

class Union_Find {
private:
	vi p, r, c; // parent, rank, the number of connected components
public:
	Union_Find(int N) {
		p.resize(N);
		r.resize(N);
		c.resize(N);
		Loop(i, N) {
			p[i] = i;
			r[i] = 0;
			c[i] = 1;
		}
	}
	int find(int x) {
		if (p[x] == x) return x;
		else return p[x] = find(p[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (r[x] == r[y]) r[x]++;
		if (r[x] < r[y]) {
			p[x] = y;
			c[y] += c[x];
		}
		else {
			p[y] = x;
			c[x] += c[y];
		}
	}
	bool is_same(int x, int y) {
		return find(x) == find(y);
	}
	int get_cnt(int x) {
		return c[find(x)];
	}
};

int main() {
	quickio();
	int n, m, q; cin >> n >> m >> q;
	vvi lst(n);
	Loop(_, m) {
		int s, t; cin >> s >> t; s--; t--;
		lst[s].push_back(t);
		lst[t].push_back(s);
	}
	Finding_Bridges *fb = new Finding_Bridges(lst);
	vector<P> bridges = fb->get_bridges();
	vector<set<int>> bst(n);
	Foreach(bridge, bridges) {
		bst[bridge.fst].insert(bridge.snd);
		bst[bridge.snd].insert(bridge.fst);
	}
	Union_Find *uf = new Union_Find(n);
	Loop(i, n) {
		Foreach(j, lst[i]) {
			if (bst[i].find(j) == bst[i].end()) {
				uf->unite(i, j);
			}
		}
	}
	vi phi(n, -1);
	tree_t T; T.n = 0;
	Loop(i, n) {
		int x = uf->find(i);
		if (phi[x] == -1) phi[x] = T.n++;
		phi[i] = phi[x];
	}
	Foreach(bridge, bridges) {
		T.edges.push_back({ phi[bridge.fst], phi[bridge.snd] });
	}
	Tree *tree = new Tree(T, 0);
	tree->solve_sprs_ancestors();
	tree->solve_hld();
	vi ss = tree->get_hld_path_sizes();
	vector<SegTreeMax*> stm(ss.size());
	Loop(i, ss.size()) {
		stm[i] = new SegTreeMax(ss[i], -1);
	}
	unordered_map<ll, int> mp;
	Loop(_, q) {
		int op; cin >> op;
		if (op == 1) {
			int u; cin >> u; u--;
			ll w; cin >> w;
			int v = phi[u];
			mp[w] = v;
			tree->nodes[v].val.push(w);
			auto pathinfos = tree->get_path_in_hld(v, v, true);
			stm[pathinfos[0].id]->upd(pathinfos[0].l, pathinfos[0].r, tree->nodes[v].val.top());
		}
		else {
			int s, t; cin >> s >> t; s--; t--;
			int a = phi[s];
			int b = phi[t];
			auto pathinfos = tree->get_path_in_hld(a, b, true);
			ll max_v = -1;
			Foreach(pathinfo, pathinfos) {
				max_v = max(max_v, stm[pathinfo.id]->maxof(pathinfo.l, pathinfo.r));
			}
			if (max_v > 0) {
				int v = mp[max_v];
				tree->nodes[v].val.pop();
				pathinfos = tree->get_path_in_hld(v, v, true);
				stm[pathinfos[0].id]->upd(pathinfos[0].l, pathinfos[0].r, tree->nodes[v].val.top());
			}
			cout << max_v << endl;
		}
	}
}
0