#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define F first
#define S second
#define PB push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vii = vector<pii>;
using vll = vector<pll>;
const int B = 150;
const int maxn = 1e5 + 5;
vector<int> from[maxn];
vii best[maxn];
int n, m, q;
void init() {
for (int u = 0; u < n; u++) {
best[u].PB({0, u});
for (int v: from[u]) {
for (pii& p: best[v]) {
best[u].PB({p.F + 1, p.S});
}
}
sort(ALL(best[u]), greater<>());
while (SZ(best[u]) > B) best[u].pop_back();
}
}
bitset<maxn> blocked;
void sol() {
cin >> n >> m >> q;
while (m--) {
int u, v;
cin >> u >> v;
from[--v].PB(--u);
}
init();
while (q--) {
int t, y;
cin >> t >> y;
--t;
vector<int> yy(y);
for (int& x: yy) {
cin >> x;
--x;
}
if (y >= B) {
vector<int> dp(t);
for (int x: yy) dp[x] = -1;
int ans = -1;
for (int i = 0; i <= t; i++) {
for (int v: from[i]) {
if (dp[v] == -1) continue;
dp[i] = max(dp[i], dp[v] + 1);
}
ans = max(ans, dp[i]);
}
cout << ans << '\n';
} else {
for (int x: yy) blocked[x] = 1;
bool ok = 0;
for (auto &[dis, v]: best[t]) {
if (!blocked[v]) {
cout << dis << '\n';
ok = 1;
break;
}
}
if (!ok) cout << -1 << '\n';
for (int x: yy) blocked[x] = 0;
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
sol();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |