#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n, d[N];
vector<int> g[N], leaf;
int tym, st[N], low[N], vis[N];
int dfs(int u, int f) {
vis[u] = 1;
low[u] = st[u] = tym++;
for(int v : g[u]) {
if(v == f) continue;
if(vis[v]) low[u] = min(low[u], st[v]);
else {
int good = dfs(v,u);
if(!good) return 0;
low[u] = min(low[u], low[v]);
}
if(d[u] < low[v]) return 0;
} return 1;
}
bool ok() {
tym = 0;
memset(vis,0,sizeof vis);
return dfs(1,-1);
}
int main() {
srand(42);
scanf("%d", &n);
for(int i = 1; i < n; i++) {
int u, v; scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
d[u]++, d[v]++;
}
for(int i = 1; i <= n; i++) if(d[i] == 1)
leaf.push_back(i);
int sz = leaf.size();
if(sz&1) leaf.push_back(leaf[0]), sz++;
printf("%d\n", sz/2);
for(;;) {
random_shuffle(leaf.begin(),leaf.end());
for(int i = 0; i < sz; i+=2) {
int u = leaf[i], v = leaf[i+1];
g[u].push_back(v);
g[v].push_back(u);
}
if(ok()) {
for(int i = 0; i < sz; i+=2)
printf("%d %d\n", leaf[i], leaf[i+1]);
return 0;
}
for(int i = 0; i < sz; i+=2) {
int u = leaf[i], v = leaf[i+1];
g[u].pop_back();
g[v].pop_back();
}
}
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
net.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14076 KB |
Output is correct |
2 |
Correct |
17 ms |
14148 KB |
Output is correct |
3 |
Correct |
13 ms |
14148 KB |
Output is correct |
4 |
Correct |
13 ms |
14148 KB |
Output is correct |
5 |
Correct |
14 ms |
14296 KB |
Output is correct |
6 |
Correct |
14 ms |
14296 KB |
Output is correct |
7 |
Correct |
14 ms |
14296 KB |
Output is correct |
8 |
Correct |
14 ms |
14296 KB |
Output is correct |
9 |
Correct |
14 ms |
14296 KB |
Output is correct |
10 |
Incorrect |
14 ms |
14360 KB |
Breaking single line is causing network to disconnect. |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14076 KB |
Output is correct |
2 |
Correct |
17 ms |
14148 KB |
Output is correct |
3 |
Correct |
13 ms |
14148 KB |
Output is correct |
4 |
Correct |
13 ms |
14148 KB |
Output is correct |
5 |
Correct |
14 ms |
14296 KB |
Output is correct |
6 |
Correct |
14 ms |
14296 KB |
Output is correct |
7 |
Correct |
14 ms |
14296 KB |
Output is correct |
8 |
Correct |
14 ms |
14296 KB |
Output is correct |
9 |
Correct |
14 ms |
14296 KB |
Output is correct |
10 |
Incorrect |
14 ms |
14360 KB |
Breaking single line is causing network to disconnect. |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14076 KB |
Output is correct |
2 |
Correct |
17 ms |
14148 KB |
Output is correct |
3 |
Correct |
13 ms |
14148 KB |
Output is correct |
4 |
Correct |
13 ms |
14148 KB |
Output is correct |
5 |
Correct |
14 ms |
14296 KB |
Output is correct |
6 |
Correct |
14 ms |
14296 KB |
Output is correct |
7 |
Correct |
14 ms |
14296 KB |
Output is correct |
8 |
Correct |
14 ms |
14296 KB |
Output is correct |
9 |
Correct |
14 ms |
14296 KB |
Output is correct |
10 |
Incorrect |
14 ms |
14360 KB |
Breaking single line is causing network to disconnect. |
11 |
Halted |
0 ms |
0 KB |
- |