#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector
const int K = 90, MAX_N = 1e5;
vec<pii> mx[MAX_N];
vec<int> adj[MAX_N], radj[MAX_N];
bool bad[MAX_N];
int dist[MAX_N];
int c[MAX_N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, m, q; cin >> n >> m >> q;
for (int i=0;i<m;i++) {
int a, b; cin >> a >> b;
adj[--a].pb(--b);
radj[b].pb(a);
}
for (int cur=0;cur<n;cur++) {
mx[cur].pb({0,cur});
map<int,int> max_u;
for (int x : radj[cur]) {
for (auto[l,y] : mx[x]) {
chmax(max_u[y],l+1);
}
}
for (auto[y,l] : max_u) {mx[cur].pb({l,y});}
sort(all(mx[cur]),greater<>());
while (mx[cur].size()>K) {mx[cur].pop_back();}
}
//for (auto[w,x] : mx[1]) {cout << x+1 << ' ' << w << '\n';}
while (q--) {
int t, y; cin >> t >> y; t--;
for (int i=0;i<y;i++) {cin >> c[i]; bad[--c[i]] = true;}
int ans = -1;
if (y<K) {
for (auto[w,x] : mx[t]) {
if (!bad[x]) {ans = w; break;}
}
} else {
memset(dist,-1,sizeof(dist));
dist[t] = 0;
for (int i=t;i>=0;i--) {
for (int x : radj[i]) {chmax(dist[x],dist[i]+1);}
if (!bad[i]) {chmax(ans,dist[i]);}
}
}
cout << ans << '\n';
for (int i=0;i<y;i++) {bad[c[i]] = false;}
}
/*
if y>=sqrt(ysum), then do o(n) brute force
if y<sqrt(ysum), then store sqrt(ysum) longest paths to each node
o(n+m sqrt(ysum))
and compare
for longest paths
it's O(MKlogMK+NK+YN/K);
MKlogMK = YN/K
NKlogNK = N^2/K
K^2(logN+logK) = N
K^2logK = N/logN
*/
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |