前言
这题断断续续做了几个小时，想假了好多次，感觉自己做构造和计数的时候并没有严谨的头脑。
不得不说感觉这题在洛谷月赛题里面质量应该是算高的。
做法
先考虑图连通怎么做。
定义与结点 \(u\) 相邻的边为存在一个端点与 \(u\) 有边相连，可以看作一条长为三的链。
首先观察到操作具有可逆性。
如果对于 \(i\) 满足 \(f(a_i,a_{i+1})=1\)，那么这两个位置可以随便选择图上的边，此时 \(a_i,a_{i+1}\) 的值并不重要，我们可以将其表示成一个特殊的“框”，随便填。
现在想想整个操作有什么比较容易利用的方式。显然你观察一个框是观察不出什么结果的，你考虑加入其相邻点，即 \([?,?],x\)。于是该问题在连通图下有以下三种操作方式：
-
你发现你可以先让它们变成与 \(x\) 相邻的边，这样我们不妨将框移到 \(y,[?,?]\)，于是你可以看作 \(x\rightarrow y\)，并且存在这条边当且仅当 \(x,y\) 之间存在长度为 \(2\) 的路径。
-
如果 \(x\) 不是孤立点，那么 \([?,?],x\) 可以变成 \(x,[?,?]\)，同理 \(x,[?,?]\) 也可以变成 \([?,?],x\)。我们只要将 \([?,?]\) 变成一个端点为 \(x\) 的边即可。这个时候我们不难发现，一个 \([?,?],x\) 后面的 \(x\) 可以变成所有它能到达的点。也就是说我们把图黑白染色后，如果存在奇环则整个图可互达，否则黑点能到黑点，白点能到白点。
-
进一步的，对于 \([?,?],x,y\) 满足 \(x,y\) 颜色不同，我们可以将 \(x\) 操作到与 \(y\) 相邻的结点，于是我们可以将 \(x,y\) 也塞入新的框内，变成 \([?,?],[?,?]\)。
现在回到问题，思考如何处理询问。
先把相同判掉。
首先一个必要条件是 \(a,b\) 都存在 \([?,?]\)。如果不满足一定不行。满足这个条件后，如果图存在奇环则一定可以。现在考虑二分图怎么做。
首先存在框之后，每个位置都能变成任意同色点，这是显然的。而无论我们怎么操作，都不会改变点的颜色，于是我们断言，此时能够达成目标的充要条件是 \(a,b\) 黑白颜色点数分别相同。证明是容易的，因为我们可以把几乎所有结点塞入框内，剩下的结点一定满足颜色相同，也就是说我们可以将每个位置的颜色任意排布。
现在考虑图不连通怎么做。
对于 \([?,?]\) 可以改成任意连通块的边，对于每一个连通块的点仍然可以使用方式一，且方式二对于全局适用。
于是不难想到先尽可能分离出更多的 \([?,?]\)，你发现策略不需要那么精细，只要分出更多的就行。那么怎么分出更多的框呢？
首先能分尽量分，分出来的框永远不会使答案和可达性变劣，我们只需要加速这个过程。不难发现我们可以使用栈来维护这个过程，我们维护栈顶的颜色和连通块，并分讨当前点与栈顶的关系。
首先如果不在同一连通块直接入栈。
否则考虑该连通块是否是二分图。如果不是则直接将栈顶弹掉。否则考察栈顶与当前点的颜色，如果颜色相同则当前点入栈。否则弹掉栈顶。
我们对 \(a,b\) 分别维护这样的栈，最后判断它们的栈是否相同即可。注意了，我们元素相等的定义是连通块相同且颜色相同，如果不是二分图则只需要判连通块。
浅证一下为啥是对的。
必要性考虑首先栈里面的这些东西是永远消不干净的。你发现你永远改变不了不同连通块的点的相对位置。就算你让你的框过去了，你也会留下一个相同颜色的点。也就是说你最后这个状态是一动不动的，所以如果不满足最后的栈相同，则一定不可能使 \(a\) 达到 \(b\)。
充分性考虑我们一定存在一种移动框的方案使得 \(a,b\) 相同。
最后特判一下孤立点，这是好判的。
代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i (l); i <= (r); ++ i)
#define rrp(i, l, r) for (int i (r); i >= (l); -- i)
#define eb emplace_back
using namespace std;
#define pii pair <long long, long long>
#define inf 1000000000000000
#define ls (p << 1)
#define rs (ls | 1)
#define fi first
#define se second
constexpr int N = 1e6 + 5, M = 2e5 + 5, P = 1e9 + 7;
typedef long long ll;
typedef unsigned long long ull;
inline ll rd () {ll x = 0, f = 1;char ch = getchar ();while (! isdigit (ch)) {if (ch == '-') f = -1;ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar ();}return x * f;
}
int qpow (int x, int y) {int ret (1);for (; y; y >>= 1, x = x * x % P) if (y & 1) ret = ret * x % P;return ret;
}
int m, k, T;
vector <int> e[N];
int n, a[N], b[N], A[N], B[N];
bool fl[N];
int col[N], idx, bel[N];
void dfs (int u, int c) {if (col[u] != -1) {if (col[u] == c) return ;fl[idx] = 1; return ;}bel[u] = idx;col[u] = c;for (auto v : e[u]) dfs (v, ! c);
}
unordered_map <int, int> mp[N];
bool vis[N];
int c[N];
pii s1[N], s2[N];
bool solve (int * a, int * b, int n) {bool flag (1), f3 (0);rep (i, 1, n) if (a[i] != b[i]) f3 = 1;if (! f3) return 1;vector <pii> vec;a[n + 1] = b[n + 1] = 0;int t1 (0), t2 (0), cnt (0);rep (i, 1, n) {if (t1) {if (s1[t1].second == bel[a[i]]) {if (s1[t1].first != col[a[i]] || fl[bel[a[i]]]) -- t1;else s1[++ t1] = pii (col[a[i]], bel[a[i]]);} else s1[++ t1] = pii (col[a[i]], bel[a[i]]);} else s1[++ t1] = pii (col[a[i]], bel[a[i]]);}rep (i, 1, n) {if (t2) {if (s2[t2].second == bel[b[i]]) {if (s2[t2].first != col[b[i]] || fl[bel[b[i]]]) -- t2;else s2[++ t2] = pii (col[b[i]], bel[b[i]]); } else s2[++ t2] = pii (col[b[i]], bel[b[i]]); } else s2[++ t2] = pii (col[b[i]], bel[b[i]]);}if (t1 != t2) return 0;rep (i, 1, t1) if (s1[i] != s2[i] && (s1[i].second != s2[i].second || ! fl[s1[i].second])) return 0;bool f1 (0), f2 (0);rep (i, 1, n - 1) {if (mp[a[i]][a[i + 1]] == 1) f1 = 1;if (mp[b[i]][b[i + 1]] == 1) f2 = 1;} return f1 && f2;
}
int32_t main () {// freopen ("1.in", "r", stdin);// freopen ("1.out", "w", stdout); memset (col, -1, sizeof col);m = rd (), k = rd (), T = rd ();rep (i, 1, m) {int u (rd ()), v (rd ());e[u].eb (v), e[v].eb (u);mp[u][v] = mp[v][u] = 1;}rep (i, 1, k) if (col[i] == -1) {++ idx;dfs (i, 0);}int cnt (0);for (; T; -- T) {++ cnt;n = rd ();int las (0);rep (i, 1, n) a[i] = rd ();rep (i, 1, n) b[i] = rd ();bool flag (0);rep (i, 1, n) {if (a[i] == b[i]) continue;if (! e[a[i]].size () || ! e[b[i]].size ()) flag = 1;}if (flag) {puts ("NO"); continue;}flag = 1;rep (i, 1, n) {if (! e[a[i]].size () || i == n) {rep (j, las + 1, i) A[j - las] = a[j], B[j - las] = b[j];flag &= solve (A, B, i - las);las = i;}}int cnt (0);puts (flag ? "YES" : "NO");}cerr << 1.0 * clock () / CLOCKS_PER_SEC << endl;
}