#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e5+10;
vector<int> adj[mxN];
set<array<int, 2>> idx[mxN], dist[mxN];
int in_deg[mxN], in_deg1[mxN], d[mxN];
bool bad[mxN], vis[mxN];
int main()
{
//freopen("02-19.txt", "r", stdin);
ios_base::sync_with_stdio(0);
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].push_back(b);
++in_deg[b]; in_deg1[b] = in_deg[b];
}
int block_size = 100;
queue<int> qe;
for(int i = 1; i <= n; i++) {
dist[i].insert({0, i});
idx[i].insert({i, 0});
}
for(int i = 1; i <= n; i++) {
if(in_deg[i] == 0) {
qe.push(i);
}
}
int cnt = 0;
while(!qe.empty()) {
int node = qe.front();
qe.pop();
++cnt;
vis[node] = true;
for(auto it : adj[node]) {
auto it1 = dist[node].begin();
while(dist[it].size() < block_size && it1 != dist[node].end()) {
array<int, 2> a = *it1; a[0]++;
auto it2 = idx[it].lower_bound({a[1], 0});
if(it2 != idx[it].end() && (*it2)[0] == a[1]) {
array<int, 2> a1 = *it2;
if(a1[1] < a[0]) {
idx[it].erase(a1);
dist[it].erase({a1[1], a1[0]});
}
else {
++it1;
continue;
}
}
dist[it].insert(a);
idx[it].insert({a[1], a[0]});
++it1;
}
while(it1 != dist[node].end()) {
auto curr = dist[it].begin();
array<int, 2> a = *curr, b = *it1; b[0]++;
++it1;
array<int, 2> a1 = {a[1], a[0]}, b1 = {b[1], 0};
auto it2 = idx[it].lower_bound(b1);
if(it2 != idx[it].end() && (*it2)[0] == b[1]) {
if((*it2)[1] < b[0]) {
idx[it].erase(it2);
dist[it].erase({(*it2)[1], (*it2)[0]});
dist[it].insert(b);
b1[1] = b[0];
idx[it].insert(b1);
}
continue;
}
b1[1] = b[0];
if(a[0] < b[0]) {
dist[it].erase(a);
dist[it].insert(b);
idx[it].erase(a1);
idx[it].insert(b1);
}
}
--in_deg[it];
if(in_deg[it] == 0) qe.push(it);
}
}
while(q--) {
int t, y;
cin >> t >> y;
vector<int> now(y);
for(int i = 0; i < y; i++) cin >> now[i];
if(y <= block_size-3) {
vector<array<int, 2>> removed;
for(auto it : now) {
auto it1 = idx[t].lower_bound({it, 0});
if(it1 != idx[t].end() && (*it1)[0] == it) {
removed.push_back(*it1);
idx[t].erase(it1);
dist[t].erase({(*it1)[1], (*it1)[0]});
}
}
if(dist[t].empty()) {
cout << -1 << '\n';
}
else {
auto ans = dist[t].end(); --ans;
cout << (*ans)[0] << '\n';
}
for(auto it : removed) {
dist[t].insert({it[1], it[0]});
idx[t].insert(it);
}
}
else {
for(int i = 1; i <= n; i++) {
in_deg[i] = in_deg1[i];
d[i] = 0;
if(in_deg[i] == 0) {
qe.push(i);
}
}
for(auto it : now) bad[it] = true;
while(!qe.empty()) {
int node = qe.front();
qe.pop();
for(auto it : adj[node]) {
--in_deg[it];
if(!bad[node]) {
d[it] = max(d[it], d[node]+1);
}
else {
if(d[node] != 0) d[it] = max(d[it], d[node]+1);
}
if(in_deg[it] == 0) qe.push(it);
}
}
if(bad[t] && d[t] == 0) cout << -1 << '\n';
else cout << d[t] << '\n';
for(auto it : now) bad[it] = false;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |