#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;
using vl = vector<ll>;
// Overload input operator for vector
istream &operator>>(istream &is, vl &a) {
for (auto &x : a) cin >> x;
return is;
}
constexpr int MAX_NODES = 200200;
constexpr int BLOCK_SIZE = 100;
vector<int> forwardGraph[MAX_NODES], reverseGraph[MAX_NODES];
// Function to process least arrays for all nodes
void preprocessLeastArrays(int n, vector<vector<pair<int, int>>> &least) {
vector<int> used(n + 1, -1);
least[1] = {{0, 1}};
for (int i = 2; i <= n; i++) {
vector<int> tempStorage;
// Traverse reverse edges
for (auto &neighbor : reverseGraph[i]) {
for (auto &[dist, node] : least[neighbor]) {
if (used[node] < 0) tempStorage.push_back(node);
used[node] = max(used[node], dist + 1);
}
}
// Update least array for node `i`
least[i].emplace_back(0, i);
for (auto &x : tempStorage) {
least[i].emplace_back(used[x], x);
}
// Sort and trim to BLOCK_SIZE
sort(least[i].begin(), least[i].end(), greater<>());
if (least[i].size() > BLOCK_SIZE) {
least[i].resize(BLOCK_SIZE);
}
// Reset `used` array
for (auto &x : tempStorage) {
used[x] = -1;
}
}
}
// Function to handle queries
void handleQuery(int t, int y, const vector<int> &blocked,
const vector<vector<pair<int, int>>> &least) {
set<int> blockedSet(blocked.begin(), blocked.end());
if (y >= BLOCK_SIZE) {
// Dynamic programming for large number of blocked nodes
vector<int> dp(t + 1, -1);
dp[t] = 0;
for (int node = t; node >= 1; node--) {
if (dp[node] == -1) continue;
for (const auto &neighbor : reverseGraph[node]) {
dp[neighbor] = max(dp[neighbor], dp[node] + 1);
}
}
int maxDistance = -1;
for (int node = 1; node <= t; node++) {
if (!blockedSet.count(node)) {
maxDistance = max(maxDistance, dp[node]);
}
}
cout << maxDistance << "\n";
} else {
// Direct computation for small number of blocked nodes
int maxDistance = -1;
for (const auto &[dist, node] : least[t]) {
if (!blockedSet.count(node)) {
maxDistance = max(maxDistance, dist);
}
}
cout << maxDistance << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
// Input graph edges
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
forwardGraph[u].push_back(v);
reverseGraph[v].push_back(u);
}
// Prepare least arrays for all nodes
vector<vector<pair<int, int>>> least(n + 1);
preprocessLeastArrays(n, least);
// Process queries
for (int i = 0; i < q; i++) {
int t, y;
cin >> t >> y;
vector<int> blocked(y);
for (int j = 0; j < y; j++) {
cin >> blocked[j];
}
handleQuery(t, y, blocked, least);
}
return 0;
}
