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
48
49
50
51
52
53
54
55
56
57
|
vector<int> graph[200001];
int n, m, result[200001], in_degree[200001];
void bfs() {
queue<int> q;
for(int i = 1; i <= n; i++) {
if(!in_degree[i]) {
q.push(i);
}
}
fill_n(result + 1, n, 0);
int now, k = 1;
while(!q.empty()) {
now = q.front(), q.pop();
result[now] = k++;
for(int child : graph[now]) {
in_degree[child]--;
if(!in_degree[child]) {
q.push(child);
}
}
}
}
struct Edge {
int u, v, type;
} edges[400000];
void solve() {
cin >> n >> m;
fill_n(in_degree + 1, n, 0);
for(int i = 1; i <= n; i++) {
graph[i].clear();
}
int k = 0;
for(int i = 0; i < m; i++, k++) {
cin >> edges[k].type >> edges[k].u >> edges[k].v;
if(edges[k].type) {
graph[edges[k].u].push_back(edges[k].v);
in_degree[edges[k].v]++;
} else {
k++;
edges[k] = {edges[k - 1].v, edges[k - 1].u, 0};
}
}
bfs();
if(count(result + 1, result + n + 1, 0)) {
cout << "NO\n";
return;
}
cout << "YES\n";
for(int i = 0; i < k; i++) {
if(edges[i].type || result[edges[i].u] < result[edges[i].v]) {
cout << edges[i].u << ' ' << edges[i].v << '\n';
}
}
}
|