#include <bits/stdc++.h> #define ll long long using namespace std; const int NMAX = 1e5; const int BSIZE = 200; int n, m, q; int v[NMAX + 1]; int dp[NMAX + 1]; vector<int> g[NMAX + 1], gt[NMAX + 1]; pair<int, int> best[NMAX + 1][BSIZE + 1]; pair<int, int> c[2 * BSIZE + 1]; int solve_heavy(int t, int k) { fill(dp + 1, dp + t + 1, 0); for(int i = 1; i <= k; i++) { dp[v[i]] = -1; } for(int i = 1; i <= t; i++) { for(int j : gt[i]) { if(dp[j] != -1) { dp[i] = max(dp[i], dp[j] + 1); } } } return dp[t]; } int solve_light(int t, int k) { unordered_set<int> s; for(int i = 1; i <= k; i++) { s.insert(v[i]); } for(int i = 1; i <= BSIZE; i++) { if(!s.count(best[t][i].second)) { return best[t][i].first; } } return -1; } void combine(pair<int, int> a[], pair<int, int> b[]) { int i = 1, j = 1, ind = 0; while(i <= BSIZE && j <= BSIZE) { if(b[j].first == -1) { j++; } else if(a[i].first > b[j].first + 1) { c[++ind] = a[i++]; } else { c[++ind] = {b[j].first + 1, b[j].second}; j++; } } while(i <= BSIZE) { c[++ind] = a[i++]; } while(j <= BSIZE) { c[++ind] = {b[j].first + 1, b[j].second}; j++; } unordered_set<int> s; ind = 0; for(int i = 1; i <= 2 * BSIZE; i++) { if(!s.count(c[i].second)) { c[++ind] = c[i]; s.insert(c[i].second); } } for(int i = 1; i <= BSIZE; i++) { a[i] = (i <= ind ? c[i] : make_pair(-1, 0)); } } void precompute() { for(int i = 1; i <= n; i++) { fill(best[i] + 1, best[i] + BSIZE + 1, make_pair(-1, 0)); best[i][1] = {0, i}; for(int j : gt[i]) { combine(best[i], best[j]); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for(int i = 1; i <= m; i++) { int a, b; cin >> a >> b; g[a].push_back(b); gt[b].push_back(a); } precompute(); while(q--) { int t, k; cin >> t >> k; for(int i = 1; i <= k; i++) { cin >> v[i]; } if(k > BSIZE) { cout << solve_heavy(t, k) << '\n'; } else { cout << solve_light(t, k) << '\n'; } } return 0; }