#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> in, ojc, ojc2, d, nr, gle;
void Resize(int n){
g.resize(n+1); gle.resize(n+1);
in.resize(n+1); nr.resize(n+1);
ojc.resize(n+1); ojc2.resize(n+1);
d.resize(n+1);
}
void dfs(int x, int o, int odl){
for(int u : g[x]) if(u != o) dfs(u, x, odl + 1);
ojc[x] = o; d[x] = odl;
}
void dfsG(int x, int o){
for(int u : g[x]) if(u != o){
dfsG(u, x);
gle[x] = max(gle[x], gle[u]);}
++gle[x];
}
int main(){
int n, m, a, b;
scanf("%d%d", &n, &m);
if(m != n-1){ printf("NO"); return 0; }
Resize(n);
for(int i = n; --i; ){
scanf("%d%d", &a, &b);
g[a].emplace_back(b);
g[b].emplace_back(a);
++in[a], ++in[b];
}
int X, Y, odl = 0;
dfs(1, 0, 0);
for(int i = 1; i <= n; ++i) if(d[i] > odl) X = i, odl = d[i];
dfs(X, 0, 0);
odl = 0;
for(int i = 1; i <= n; ++i) if(d[i] > odl) Y = i, odl = d[i];
dfsG(Y, 0);
vector<int> ans;
for(int x = Y; x; x = ojc[x]){
ojc2[ojc[x]] = x;
if(x == X || x == Y) continue;
ans.emplace_back(x);
for(int u : g[x]) if(u != ojc[x] && u != ojc2[x]){
if(gle[u] > 2) { printf("NO"); return 0; }
else if(gle[u] == 1) continue;
ans.emplace_back(u);
ans.emplace_back(x);
}
}
for(int x = X; x; x = ojc2[x]){
if(x == X || x == Y) continue;
ans.emplace_back(x);
for(int u : g[x]) if(u != ojc[x] && u != ojc2[x]){
if(gle[u] == 1) continue;
ans.emplace_back(u);
ans.emplace_back(x);
}
//printf("%d ", x);
}
printf("YES\n%d\n", (int) ans.size());
for(int u : ans) printf("%d ", u);
return 0;
}
Compilation message
newspapers.cpp: In function 'int main()':
newspapers.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
newspapers.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
newspapers.cpp:63:15: warning: 'Y' may be used uninitialized in this function [-Wmaybe-uninitialized]
63 | if(x == X || x == Y) continue;
| ~~~~~~~^~~~~~~~~
newspapers.cpp:62:11: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | for(int x = X; x; x = ojc2[x]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
