#include <bits/stdc++.h> using namespace std; using pii = pair<int,int>; using ll = long long; const int NMAX = 100000; const int BSIZE = 100; int n, m, q; int v[NMAX + 5]; int dp[NMAX + 5]; vector<int> g[NMAX + 5], gt[NMAX + 5]; pii best[NMAX + 5][BSIZE + 2]; // temporaries for combine static pii tmp_arr[2 * BSIZE + 5]; static pii out_arr[BSIZE + 2]; // timestamp trick to avoid unordered_set and clearing costs static int seen_node[NMAX + 5]; static int seen_stamp = 1; int solve_heavy(int t, int k) { // standard DP over incoming edges for(int i = 1; i <= t; ++i) dp[i] = 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) { // use stamp array instead of unordered_set ++seen_stamp; if(seen_stamp == 0) { // wrap-around safety memset(seen_node, 0, sizeof(seen_node)); seen_stamp = 1; } for(int i = 1; i <= k; ++i) seen_node[v[i]] = seen_stamp; for(int i = 1; i <= BSIZE; ++i) { if(best[t][i].first == -1) break; if(seen_node[best[t][i].second] != seen_stamp) return best[t][i].first; } return -1; } inline void combine(pii a[], pii b[]) { int i = 1, j = 1, ind = 0; // merge-like combine, but b's value is shifted by +1 in first while(i <= BSIZE && j <= BSIZE) { if(b[j].first == -1) { ++j; continue; } if(a[i].first == -1) { // all remaining a are -1, just take shifted b's tmp_arr[++ind] = {b[j].first + 1, b[j].second}; ++j; continue; } if(a[i].first > b[j].first + 1) { tmp_arr[++ind] = a[i++]; } else { tmp_arr[++ind] = {b[j].first + 1, b[j].second}; ++j; } } while(i <= BSIZE) { if(a[i].first == -1) break; tmp_arr[++ind] = a[i++]; } while(j <= BSIZE) { if(b[j].first == -1) { ++j; continue; } tmp_arr[++ind] = {b[j].first + 1, b[j].second}; ++j; } // deduplicate preserving order using seen_node + stamp ++seen_stamp; if(seen_stamp == 0) { // wrap-around safety memset(seen_node, 0, sizeof(seen_node)); seen_stamp = 1; } int outc = 0; for(int k = 1; k <= ind && outc < BSIZE; ++k) { int node = tmp_arr[k].second; if(seen_node[node] != seen_stamp) { seen_node[node] = seen_stamp; out_arr[++outc] = tmp_arr[k]; } } // write back to a[] for(int p = 1; p <= BSIZE; ++p) { if(p <= outc) a[p] = out_arr[p]; else a[p] = make_pair(-1, 0); } } void precompute() { // initialize best arrays for(int i = 1; i <= n; ++i) { for(int j = 1; j <= BSIZE; ++j) best[i][j] = make_pair(-1, 0); best[i][1] = {0, i}; } // combine for each incoming neighbor for(int i = 1; i <= n; ++i) { for(int j : gt[i]) { combine(best[i], best[j]); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q; for(int i = 0; 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; }