1889E - Doremy's Swapping Trees - CodeForces Solution

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
using namespace std;
int n, tot, ac;
namespace G {
const int N = 8e6 + 7;
int vis[N], low[N], dfn[N], cnt, bh[N], top, stk[N], idt;
int ehd[N], ev[N], enx[N], eid;
void eadd(int u, int v) {
	++eid, ev[eid] = v, enx[eid] = ehd[u], ehd[u] = eid;
}
void dfs(int x) {
	low[x] = dfn[x] = ++idt, stk[++top] = x, vis[x] = 1;
	for(int i = ehd[x]; i; i = enx[i]) {
		if(!dfn[ev[i]]) dfn[ev[i]] = dfn[x] + 1, dfs(ev[i]);
		if(vis[ev[i]]) low[x] = min(low[x], low[ev[i]]);
	}
	if(dfn[x] == low[x]) {
		int mn = 1e9;
		for(int u = 0; u != x; ) 
			u = stk[top], bh[u] = cnt, vis[u] = 0, --top, mn = min(mn, u);
		if(mn <= n * 2 - 2) 
			++ac;
	}
}
void clear(int n) {
	eid = 0, cnt = 0, idt = 0;
	L(i, 1, n) ehd[i] = 0, low[i] = dfn[i] = vis[i] = bh[i] = 0;
}
}
const int N = 2e5 + 7, mod = 1e9 + 7;

vector < pair < int, int > > e[N], vc[N];
void add(int u, int v, int i) {
	e[u].emplace_back(v, i);
	e[v].emplace_back(u, i);
}
void link(int x, int y, int p) {
	vc[x].emplace_back(y, p);
	vc[y].emplace_back(x, p);
}
int f[N], val[N];
void find(int x) {
	if(x == f[x]) return;
	find(f[x]);
	if(f[f[x]] != f[x]) 
		++tot, G :: eadd(tot, val[x]), G :: eadd(tot, val[f[x]]), val[x] = tot;
	f[x] = f[f[x]];
}

int vis[N];
void dfs(int x, int fa) {
	reverse(e[x].begin(), e[x].end());
	for(auto&v : e[x]) if(v.first != fa) 
		dfs(v.first, x), f[v.first] = x, val[v.first] = v.second;
	for(auto&q : vc[x]) 
		if(vis[q.first]) 
			find(q.first), G :: eadd(q.second, val[q.first]);
	vis[x] = 1;
}

void Main() {
	cin >> n;
	tot = n * 2 - 2;
	map < pair < int, int >, int > mp;
	L(i, 1, n * 2 - 2) {
		int u, v;
		cin >> u >> v; 
		if(u > v) swap(u, v);
		mp[make_pair(u, v)] += 1;
		if(i <= n - 1) {
			add(u, v, i);
			link(u + n, v + n, i);
		} else {
			add(u + n, v + n, i);
			link(u, v, i);
		}
	}
	L(c, 0, 1) {
		L(i, 0, n * 2) vis[i] = 0, f[i] = i; 
		dfs(1, 0), dfs(n + 1, 0);
	}
	ac = 0;
	L(i, 1, n * 2 - 2) if(!G :: dfn[i]) G :: dfs(i);
	
	int ans = 1, c = ac;
	for(auto&e : mp) 
		if(e.second == 2) 
			--c;
	L(i, 1, c) ans = (ll) ans * 2 % mod;
	cout << ans << '\n';
	G :: clear(tot);
	
	L(i, 1, n * 2) e[i].clear(), vc[i].clear(), f[i] = 0, vis[i] = 0, val[i] = 0;
}
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
}