#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
const int B = 150; // Threshold for small/large Y_j
vector<int> graph[MAX_N]; // Original graph (u -> v)
vector<pair<int, int>> longestPaths[MAX_N]; // longestPaths[u]: top B paths (distance, node)
bool isForbidden[MAX_N]; // Marks forbidden nodes during queries
bool visited[MAX_N]; // Temporary marker for mergePaths
// Merges two path lists and keeps top B paths
vector<pair<int, int>> mergePaths(const vector<pair<int, int>>& pathsA,
const vector<pair<int, int>>& pathsB) {
vector<pair<int, int>> merged;
int i = 0, j = 0;
while ((i < pathsA.size() || j < pathsB.size()) && merged.size() < B) {
if (i == pathsA.size()) {
if (!visited[pathsB[j].second]) {
visited[pathsB[j].second] = true;
merged.push_back(pathsB[j]);
}
j++;
continue;
}
if (j == pathsB.size()) {
if (!visited[pathsA[i].second]) {
visited[pathsA[i].second] = true;
merged.push_back({pathsA[i].first + 1, pathsA[i].second});
}
i++;
continue;
}
if (pathsA[i].first + 1 > pathsB[j].first) {
if (!visited[pathsA[i].second]) {
visited[pathsA[i].second] = true;
merged.push_back({pathsA[i].first + 1, pathsA[i].second});
}
i++;
} else {
if (!visited[pathsB[j].second]) {
visited[pathsB[j].second] = true;
merged.push_back(pathsB[j]);
}
j++;
}
}
// Reset visited markers
for (const auto& p : merged) visited[p.second] = false;
return merged;
}
// Computes longest paths from all nodes to 'target' (skipping forbidden nodes)
int computeLongestPath(int target, const vector<int>& forbiddenNodes) {
vector<int> maxDistance(MAX_N, -1);
vector<bool> isAllowed(MAX_N, true);
// Mark forbidden nodes
for (int node : forbiddenNodes) isAllowed[node] = false;
// Initialize DP
maxDistance[target] = 0;
// Process nodes in topological order (simplified)
for (int u = 1; u < MAX_N; u++) {
if (maxDistance[u] >= 0 && isAllowed[u]) {
for (int v : graph[u]) {
if (isAllowed[v]) {
maxDistance[v] = max(maxDistance[v], maxDistance[u] + 1);
}
}
}
}
// Find maximum distance among allowed nodes
int result = -1;
for (int u = 1; u < MAX_N; u++) {
if (isAllowed[u]) result = max(result, maxDistance[u]);
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
// Build graph
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
// Preprocess top B longest paths for each node
for (int u = 1; u <= n; u++) {
if (longestPaths[u].size() < B) {
longestPaths[u].push_back({0, u});
}
for (int v : graph[u]) {
longestPaths[v] = mergePaths(longestPaths[u], longestPaths[v]);
}
}
// Process queries
while (q--) {
int target, k;
cin >> target >> k;
vector<int> forbiddenNodes(k);
for (int i = 0; i < k; i++) cin >> forbiddenNodes[i];
if (k >= B) {
// Large Y_j: Compute longest path dynamically
cout << computeLongestPath(target, forbiddenNodes) << "\n";
} else {
// Small Y_j: Use preprocessed paths
for (int node : forbiddenNodes) isForbidden[node] = true;
int maxDist = -1;
for (const auto& p : longestPaths[target]) {
if (!isForbidden[p.second]) {
maxDist = p.first;
break;
}
}
for (int node : forbiddenNodes) isForbidden[node] = false;
cout << maxDist << "\n";
}
}
return 0;
}
