Description
为了再现那日的彗星，Nana 和 Lily 需要使用特定的数对把一个序列变成另一个序列。
Nana 有一个长度为 \(n\) 序列 \(a\)，Lily 每次可以选择一个下标 \(i(1\le i<n)\)，然后操作 \(a_i\leftarrow x,a_{i+1}\leftarrow y\)。
选定的 \(1\le x,y\le k\) 需要满足 \(f(a_i,a_{i+1})=f(x,y)=1\)。Lily 最后需要把 \(a\) 变成另一个长度为 \(n\) 的序列 \(b\)。
其中，Nana 将给出一个 \(k\) 个点 \(m\) 条边的无向图 \(G\)，不保证没有重边和自环，则 \(f(x,y)=1\) 当且仅当图上 \(x\) 与 \(y\) 之间存在连边。需要注意的是，如果有 \(x\) 与 \(x\) 之间的连边（一个自环）则 \(f(x,x)=1\)，否则 \(f(x,x)=0\)。
Lily 并不太关心构造的方案，所以她想让你多组测试询问 \(a\) 是否能变成另一个长度为 \(n\) 的序列 \(b\)。
\(1\le T\le 10^4,2\le n\le 10^5,\sum n\le 10^6,1\le m\le 3\times 10^5,1\le k\le 2\times 10^5\)。
不保证图没有重边和自环。
Solution
首先如果存在一个 \(a_i\) 是孤立点，则 \(a_i\) 一定不会移动，所以可以把这些孤立点判掉。同时如果序列中目前不存在任何边，则完全不能操作，也判掉。
现在假设所有 \(a_i\) 和 \(b_i\) 都不是孤立点且存在至少一条边。
现有的操作还是太弱，考虑找一些好用的组合操作。如果现在存在一个子段 \([x,u,v]\)，其中 \((u,v)\) 是一条边。由于 \(x\) 不是孤立点，所以一定存在两条边是 \((x,y)\) 和 \((y,z)\)，那么我们可以做一些操作：\([x,u,v]\to[x,y,x]\to[u,v,x]\)，以及 \([x,u,v]\to[x,y,x]\to[z,y,x]\to[z,u,v]\)。
这两个操作的含义就是可以让一条已经存在的边随意移动，以及可以让这条边旁边的点在图上任意走偶数步。
所以如果初始存在至少一条边，我们就可以让序列中的所有点在图上任意走偶数步。根据这个结论可以推出如果相邻的 \(a_i\) 和 \(a_{i+1}\) 可以通过走奇数步互相到达，则可以看成新加了一条 \((a_i,a_{i+1})\) 的边。
然后考虑怎么判定两个序列能够互相操作得到。注意到操作可逆，所以策略是每次找到一对相邻的 \(a_i\) 和 \(a_{i+1}\)，如果它们可以走奇数步互相到达，就把 \(a_i\) 和 \(a_{i+1}\) 删掉。
让两个序列都按照上面的策略做最多的操作次数，假设最后剩下的点为 \(c_1,c_2,\ldots,c_{t_1}\) 和 \(d_1,d_2,\ldots,d_{t_2}\)，判断 \(t_1=t_2\) 以及 \(c_i\) 和 \(d_i\) 都能通过走偶数步互相到达。
操作出剩余的点数显然要相同，但是最后剩下的 \(c\) 数组不一定固定，就不好判断了。
注意到走偶数步能互相到达的点是互相等价的，所以每个点可以看成一个带颜色的括号，每次选择颜色相同的括号进行匹配。这是个比较典的问题，维护一个栈，新加入一个括号的时候判断和栈顶能不能匹配，能匹配的就弹栈，否则把新加入的括号加入栈中。
最终剩下的栈一定是唯一的，所以判断两个序列做匹配剩余的栈是否等价即可。
时间复杂度：\(O((n+m)\log k+k)\)。
Solution
#include <bits/stdc++.h>// #define int int64_tconst int kMaxN = 3e5 + 5;int n, m, k;
int a[kMaxN], b[kMaxN];
bool vis[kMaxN];
std::unordered_map<int, bool> mp[kMaxN];struct DSU {int fa[kMaxN * 2];void init(int n) { std::iota(fa + 1, fa + 1 + n, 1); }int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }void unionn(int x, int y) {int fx = find(x), fy = find(y);if (fx != fy) fa[fx] = fy;}
} dsu;void prework() {dsu.init(2 * k);for (int i = 1; i <= m; ++i) {int u, v;std::cin >> u >> v;mp[u][v] = mp[v][u] = 1;dsu.unionn(u, v + k), dsu.unionn(v, u + k);vis[u] = vis[v] = 1;}
}std::vector<int> getstk(int n, int *a) {std::vector<int> stk;for (int i = 1; i <= n; ++i) {if (stk.size() && dsu.find(stk.back() + k) == dsu.find(a[i])) stk.pop_back();else stk.emplace_back(a[i]);}return stk;
}void dickdreamer() {std::cin >> n;for (int i = 1; i <= n; ++i) std::cin >> a[i];for (int i = 1; i <= n; ++i) std::cin >> b[i];for (int i = 1; i <= n; ++i)if (vis[a[i]] != vis[b[i]] || !vis[a[i]] && a[i] != b[i])return void(std::cout << "NO\n");for (int i = 1, lst = 0; i <= n + 1; ++i) {if (i == n + 1 || !vis[a[i]]) {bool fla = 0, flb = 0;for (int j = lst + 1; j < i - 1; ++j) {if (mp[a[j]].count(a[j + 1])) fla = 1;if (mp[b[j]].count(b[j + 1])) flb = 1;}if (!fla || !flb) {for (int j = lst + 1; j <= i - 1; ++j)if (a[j] != b[j])return void(std::cout << "NO\n");} else {auto stka = getstk(i - lst - 1, a + lst), stkb = getstk(i - lst - 1, b + lst);if (stka.size() != stkb.size()) return void(std::cout << "NO\n");for (int j = 0; j < stka.size(); ++j)if (dsu.find(stka[j]) != dsu.find(stkb[j]))return void(std::cout << "NO\n");}lst = i;}}std::cout << "YES\n";
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;std::cin >> m >> k >> T;prework();while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}