#include <bits/stdc++.h> #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> #include <numeric> #include <stack> #include <chrono> using namespace std; void fast_io(){ // freopen("", "r", stdin); // freopen("", "w", stdout); ios::sync_with_stdio(0); cin.tie(); cout.tie(); cout << setprecision(9); } #define int long long #define endl '\n' #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define fi first #define se second const int N = 1e5 + 5; int n, m, q, indeg[N]; vector<int> adj[N]; vector<pair<int, int>> L[N]; vector<pair<int,int>> merge(const vector<pair<int,int>>& A, const vector<pair<int,int>>& B) { static pair<int,int> tmp[700]; // temporary buffer int k = 0; for(auto &x : A) tmp[k++] = {x.first + 1, x.second}; for(auto &y : B) tmp[k++] = {y.first, y.second}; sort(tmp, tmp + k, [](auto &a, auto &b){ return a.second < b.second; }); vector<pair<int,int>> out; out.reserve(300); for(int i = 0; i < k; ) { int src = tmp[i].second, best = tmp[i].first, j = i + 1; while(j < k && tmp[j].second == src) { best = max(best, tmp[j].first); j++; } out.push_back({best, src}); i = j; } sort(out.rbegin(), out.rend()); // sort descending by length if(out.size() > 300) out.resize(300); return out; } void init(){ int IN[N]; for (int i = 1; i <= n; i++) IN[i] = indeg[i]; queue<int> q; for (int i = 1; i <= n; i++){ L[i].push_back({0, i}); if (IN[i] == 0) q.push(i); } while (q.size()){ int u = q.front(); q.pop(); for (auto v : adj[u]){ L[v] = merge(L[u], L[v]); --IN[v]; if (IN[v] == 0) q.push(v); } } } void solve() { cin >> n >> m >> q; for (int i = 1; i <= m; i++){ int u, v; cin >> u >> v; indeg[v]++; adj[u].push_back(v); } init(); for (int i = 1; i <= n; i++) sort(rall(L[i])); for (int Q = 1; Q <= q; Q++){ int T, Y; cin >> T >> Y; int C[Y + 1]; map<int, bool> c; for (int i = 1; i <= Y; i++) { cin >> C[i]; c[C[i]] = 1; } if (Y <= 300) { bool bb = 0; int S = min(300ll, (int) L[T].size()); for (int i = 0; i < S; i++){ if (!c[L[T][i].second]){ cout << L[T][i].first << endl; bb = 1; break; } } if (!bb) cout << -1 << endl; } else { queue<int> q; int IN[N] = {}, ans[N] = {}; for (int i = 1; i <= Y; i++){ ans[C[i]] = -1e18; } for (int i = 1; i <= n; i++) IN[i] = indeg[i]; for (int i = 1; i <= n; i++){ if (IN[i] == 0) q.push(i); } while (q.size()){ int u = q.front(); q.pop(); for (auto v : adj[u]){ ans[v] = max(ans[v], ans[u] + 1); IN[v]--; if (IN[v] == 0) q.push(v); } } if (ans[T] < 0) cout << -1 << endl; else cout << ans[T] << endl; } } return; } signed main() { fast_io(); srand(chrono::steady_clock::now().time_since_epoch().count()); int tc = 1; // cin >> tc; while (tc--) solve(); return 0; }