1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
const int MX = 1e5+5;
int ans[MX];
vector<ii> E, G[MX];
void dfs(int u) {
for (ii v : G[u]) if (ans[v.s] < min(v.f, ans[u])) {
ans[v.s] = min(v.f, ans[u]);
dfs(v.s);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, Q; cin >> N >> Q;
fill(ans+1, ans+N+1, Q);
for (int i = 0; i < Q; ++i) {
char c; cin >> c;
if (c == 'D') {
int x; cin >> x;
ans[x] = i;
}
else if (c == 'A') {
int x, y; cin >> x >> y;
E.emplace_back(x, y);
}
else {
int e; cin >> e;
int u = E[e-1].f, v = E[e-1].s;
G[u].emplace_back(i, v), G[v].emplace_back(i, u);
E[e-1].f = -1;
}
}
for (ii & p : E) if (p.f != -1)
G[p.f].emplace_back(Q, p.s), G[p.s].emplace_back(Q, p.f);
vector<ii> vc;
for (int i = 1; i <= N; ++i) vc.emplace_back(ans[i], i);
sort(begin(vc), end(vc), greater<>());
for (ii & p : vc) dfs(p.s);
for (int i = 1; i <= N; ++i) cout << ans[i] << '\n';
}
|
