#include <bits/stdc++.h> using namespace std; #define int long long const int N = 100010, B = 500; vector<pair<int,int>> merge(vector<pair<int,int>> &tobe, vector<pair<int,int>> &merged){ vector<pair<int,int>> res; vector<int> jafoi(N); int p1 = 0, p2 = 0, size1 = tobe.size(), size2 = merged.size(), ct = 0; while(ct < B && (p1 < size1 || p2 < size2)){ if(p2 == size2){ // cout << "1 " << p1 << " " << p2 << endl; if(!jafoi[tobe[p1].second]){ jafoi[tobe[p1].second] = 1; res.push_back(tobe[p1]); ct++; // cout << "ebaaa1 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl; } p1++; } else if(p1 == size1){ // cout << "2 " << p1 << " " << p2 << endl; if(!jafoi[merged[p2].second]){ jafoi[merged[p2].second] = 1; res.push_back({merged[p2].first + 1, merged[p2].second}); ct++; // cout << "ebaaa2 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl; } p2++; } else if(tobe[p1].first > merged[p2].first + 1){ // cout << "3 " << p1 << " " << p2 << endl; if(!jafoi[tobe[p1].second]){ jafoi[tobe[p1].second] = 1; res.push_back(tobe[p1]); ct++; // cout << "ebaaa3 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl; } p1++; } else{ // cout << "4 " << p1 << " " << p2 << endl; if(!jafoi[merged[p2].second]){ jafoi[merged[p2].second] = 1; res.push_back({merged[p2].first + 1, merged[p2].second}); ct++; // cout << "ebaaa4 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl; } p2++; } } return res; } signed main(){ int n, m, q; cin >> n >> m >> q; vector<vector<int>> nei(n, vector<int>(0)); // .f = dist ,,, .s = id for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; nei[a-1].push_back(b-1); } vector<vector<pair<int,int>>> dist(n, vector<pair<int,int>>(0)); for(int i = 0; i < n; i++) dist[i].push_back({(int)0,i}); for(int i = 0; i < n; i++){ for(auto v : nei[i]){ dist[v] = merge(dist[v], dist[i]); } } // for(int i = 0; i < n; i++){ // cout << i+1 << ":\n"; // for(auto [distance, frie] : dist[i]){ // cout << distance << " " << frie+1 << endl; // } // cout << "\n\n"; // } for(int i = 0; i < q; i++){ int cid, bloq; cin >> cid >> bloq; cid--; vector<bool> block(N); for(int j = 0; j < bloq;j++){ int x; cin >> x; block[x-1] = true; } // cout << "\n\noioi"; // for(int j = 0; j < n; j++) cout << block[j] << endl; // cout << "\n\n"; if(bloq > B){ vector<pair<int,int>> maior(n); for(int j = 0; j < n; j++) maior[j] = {0,j}; for(int j = 0; j < cid; j++){ for(auto cur : nei[j]){ if(!block[maior[j].second] && maior[j].first + 1 > maior[cur].first){ maior[cur] = {maior[j].first + 1, maior[j].second}; // cout << j+1<< " atualizando " << cur+1 << " " << maior[cur].first << " "<< maior[cur].second+1 << "\n"; } } } if(!block[maior[cid].second]) cout << maior[cid].first << "\n"; else cout << -1 << "\n"; } else{ // cout << cid+1 << " " << bloq << " "; bool a = true; for(auto [distance, frie] : dist[cid]){ if(!block[frie]){ cout << distance << endl; a = false; break; } } if(a) cout << -1 << endl; } } }