#include<iostream>
#include<map>
#include<array>
#include<chrono>
#include<random>
#include<cassert>
using namespace std;
#line 2 "string/rolling-hash.hpp"
#include <string>
#include <vector>
using namespace std;
#line 2 "internal/internal-hash.hpp"
namespace internal {
using i64 = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;
template <int BASE_NUM = 2>
struct Hash : array<u64, BASE_NUM> {
using array<u64, BASE_NUM>::operator[];
static constexpr int n = BASE_NUM;
Hash() : array<u64, BASE_NUM>() {}
static constexpr u64 md = (1ull << 61) - 1;
constexpr static Hash set(const i64 &a) {
Hash res;
fill(begin(res), end(res), cast(a));
return res;
}
Hash &operator+=(const Hash &r) {
for (int i = 0; i < n; i++)
if (((*this)[i] += r[i]) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator+=(const i64 &r) {
u64 s = cast(r);
for (int i = 0; i < n; i++)
if (((*this)[i] += s) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator-=(const Hash &r) {
for (int i = 0; i < n; i++)
if (((*this)[i] += md - r[i]) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator-=(const i64 &r) {
u64 s = cast(r);
for (int i = 0; i < n; i++)
if (((*this)[i] += md - s) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator*=(const Hash &r) {
for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], r[i]);
return *this;
}
Hash &operator*=(const i64 &r) {
u64 s = cast(r);
for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], s);
return *this;
}
Hash operator+(const Hash &r) { return Hash(*this) += r; }
Hash operator+(const i64 &r) { return Hash(*this) += r; }
Hash operator-(const Hash &r) { return Hash(*this) -= r; }
Hash operator-(const i64 &r) { return Hash(*this) -= r; }
Hash operator*(const Hash &r) { return Hash(*this) *= r; }
Hash operator*(const i64 &r) { return Hash(*this) *= r; }
Hash operator-() const {
Hash res;
for (int i = 0; i < n; i++) res[i] = (*this)[i] == 0 ? 0 : md - (*this)[i];
return res;
}
friend Hash pfma(const Hash &a, const Hash &b, const Hash &c) {
Hash res;
for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], c[i]);
return res;
}
friend Hash pfma(const Hash &a, const Hash &b, const i64 &c) {
Hash res;
u64 s = cast(c);
for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], s);
return res;
}
Hash pow(long long e) {
Hash a{*this}, res{Hash::set(1)};
for (; e; a *= a, e >>= 1) {
if (e & 1) res *= a;
}
return res;
}
static Hash get_basis() {
static auto rand_time =
chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count();
static mt19937_64 rng(rand_time);
Hash h;
for (int i = 0; i < n; i++) {
while (isPrimitive(h[i] = rng() % (md - 1) + 1) == false)
;
}
return h;
}
private:
static u64 modpow(u64 a, u64 b) {
u64 r = 1;
for (a %= md; b; a = modmul(a, a), b >>= 1) r = modmul(r, a);
return r;
}
static bool isPrimitive(u64 x) {
for (auto &d : vector<u64>{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321})
if (modpow(x, (md - 1) / d) <= 1) return false;
return true;
}
static inline constexpr u64 cast(const long long &a) {
return a < 0 ? a + md : a;
}
static inline constexpr u64 modmul(const u64 &a, const u64 &b) {
u128 d = u128(a) * b;
u64 ret = (u64(d) & md) + u64(d >> 61);
return ret >= md ? ret - md : ret;
}
static inline constexpr u64 modfma(const u64 &a, const u64 &b, const u64 &c) {
u128 d = u128(a) * b + c;
u64 ret = (d >> 61) + (u64(d) & md);
return ret >= md ? ret - md : ret;
}
};
} // namespace internal
/**
* @brief 繝上ャ繧ｷ繝･讒矩菴・ * @docs docs/internal/internal-hash.md
*/
#line 8 "string/rolling-hash.hpp"
template <typename Str, int BASE_NUM = 2>
struct RollingHash {
using Hash = internal::Hash<BASE_NUM>;
Str data;
vector<Hash> hs, pw;
int s;
static Hash basis;
RollingHash(const Str &S = Str()) { build(S); }
void build(const Str &S) {
data = S;
s = S.size();
hs.resize(s + 1);
pw.resize(s + 1);
pw[0] = Hash::set(1);
hs[0] = Hash::set(0);
for (int i = 1; i <= s; i++) {
pw[i] = pw[i - 1] * basis;
hs[i] = pfma(hs[i - 1], basis, S[i - 1]);
}
}
Hash get(int l, int r = -1) const {
if (r == -1) r = s;
return pfma(hs[l], -pw[r - l], hs[r]);
}
// T 縺ｮ hash 繧定ｿ斐☆
static Hash get_hash(const Str &T) {
Hash ret = Hash::set(0);
for (int i = 0; i < (int)T.size(); i++) ret = pfma(ret, basis, T[i]);
return ret;
}
// a + b 縺ｮ hash 繧定ｿ斐☆
// 蠑墓焚 : a, b, b 縺ｮ髟ｷ縺・ static Hash unite(Hash a, Hash b, long long bsize) {
return pfma(a, basis.pow(bsize), b);
}
int find(Str &T, int lower = 0) const {
auto ths = get_hash(T);
for (int i = lower; i <= s - (int)T.size(); i++)
if (ths == get(i, i + (int)T.size())) return i;
return -1;
}
static int lcp(const RollingHash &a, const RollingHash &b, int al, int bl) {
int ok = 0, ng = min(a.size() - al, b.size() - bl) + 1;
while (ok + 1 < ng) {
int med = (ok + ng) / 2;
(a.get(al, med + al) == b.get(bl, med + bl) ? ok : ng) = med;
}
return ok;
}
static int strcmp(const RollingHash &a, const RollingHash &b, int al, int bl,
int ar = -1, int br = -1) {
if (ar == -1) ar = a.size();
if (br == -1) br = b.size();
int n = min<int>({lcp(a, b, al, bl), ar - al, br - bl});
return al + n == ar ? bl + n == br ? 0 : -1
: bl + n == br ? 1
: a.data[al + n] < b.data[bl + n] ? -1
: 1;
}
int size() const { return s; }
};
template <typename Str, int BASE_NUM>
typename RollingHash<Str, BASE_NUM>::Hash RollingHash<Str, BASE_NUM>::basis =
internal::Hash<BASE_NUM>::get_basis();
using roriha = RollingHash<vector<int>, 2>;
/**
* @brief Rolling Hash
* @docs docs/string/rolling-hash.md
*/
int N,M,Q;
int I[1<<17],J[1<<17];
vector<int>B[1<<17],pos[1<<17];
int cnt[1<<17],ans[1<<17];
vector<pair<int,int> >qi[1<<17];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N>>M>>Q;
const int LIM=50;
if(N<LIM)
{
vector<int>A(N);
for(int i=1;i<=N;i++)A[i-1]=i;
map<roriha::Hash,int>mp[LIM];
roriha H(A);
for(int i=0;i<N;i++)for(int j=i+1;j<=N;j++)
{
roriha::Hash h=H.get(i,j);
int k=j-i;
if(mp[k].find(h)==mp[k].end())mp[k][h]=0;
}
for(int q=1;q<=M;q++)
{
int i,j;cin>>i>>j;i--,j--;
swap(A[i],A[j]);
roriha H(A);
for(int i=0;i<N;i++)for(int j=i+1;j<=N;j++)
{
roriha::Hash h=H.get(i,j);
int k=j-i;
if(mp[k].find(h)==mp[k].end())mp[k][h]=q;
}
}
for(int i=0;i<Q;i++)
{
int k;cin>>k;
vector<int>B(k);
for(int j=0;j<k;j++)cin>>B[j];
auto h=roriha::get_hash(B);
cout<<mp[k][h]<<"\n";
}
return 0;
}
for(int q=1;q<=M;q++)
{
cin>>I[q]>>J[q];
I[q]--,J[q]--;
}
for(int i=0;i<Q;i++)
{
int k;cin>>k;
B[i].resize(k);
pos[i].resize(k);
for(int j=0;j<k;j++)
{
cin>>B[i][j];
qi[B[i][j]].push_back(make_pair(i,j));
pos[i][j]=B[i][j]-1;
}
cnt[i]=0;
ans[i]=-1;
for(int j=1;j<k;j++)if(pos[i][j-1]+1==pos[i][j])cnt[i]++;
if(cnt[i]==k-1)ans[i]=0;
}
vector<int>A(N);
for(int i=1;i<=N;i++)A[i-1]=i;
for(int q=1;q<=M;q++)
{
for(int t=0;t<2;t++)
{
swap(I[q],J[q]);
int x=A[I[q]],y=A[J[q]];
for(auto[i,j]:qi[x])
{
assert(pos[i][j]==I[q]);
if(j>=1&&pos[i][j-1]+1==pos[i][j])cnt[i]--;
if(j+1<B[i].size()&&pos[i][j]+1==pos[i][j+1])cnt[i]--;
pos[i][j]=J[q];
if(j>=1&&pos[i][j-1]+1==pos[i][j])cnt[i]++;
if(j+1<B[i].size()&&pos[i][j]+1==pos[i][j+1])cnt[i]++;
}
}
swap(A[I[q]],A[J[q]]);
for(int x:{A[I[q]],A[J[q]]})for(auto[i,j]:qi[x])if(ans[i]==-1&&cnt[i]==B[i].size()-1)ans[i]=q;
}
for(int i=0;i<Q;i++)cout<<ans[i]<<"\n";
}