#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
int n, m;
vector<int> adj[1029];
int dp[1029];
void dpf(int node, int prv) {
dp[node] = 1;
for(int x: adj[node]) {
if(adj[x].size() == 1) continue;
if(x == prv) continue;
dpf(x, node);
dp[node] += dp[x];
}
}
vector<int> dfs(int node, int prv) {
int ct=0;
vector<pair<int, int> > vt;
for(int x: adj[node]) {
if(x != prv && adj[x].size() > 1) {
ct += (dp[x] > 1);
vt.push_back({dp[x], x});
}
}
if(ct > 2) {
return {-1};
}
if(prv != -1 && ct > 1) {
return {-1};
}
sort(vt.begin(), vt.end());
if(vt.empty()) {
return {node};
}
int to = vt[vt.size() - 1].second;
vector<int> res;
res = dfs(to, node);
if(res[0] == to) reverse(res.begin(), res.end());
res.push_back(node);
for(int i=0; i+1<vt.size(); i++) {
to = vt[i].second;
vector<int> get = dfs(to, node);
if(get[0] != to) reverse(get.begin(), get.end());
for(int x: get) res.push_back(x);
if(!(prv == -1 && i+2 == vt.size()))res.push_back(node);
}
for(int x: res) if(x == -1) return {-1};
return res;
}
void solve(int tc) {
cin >> n >> m;
for(int i=0; i<m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if(m != n-1) {
cout << "NO\n"; return;
}
if(n == 2) {
cout << "YES\n2\n1 1\n"; return;
}
for(int rt=1; rt<=n; rt++) {
if(adj[rt].size() > 1) {
for(int i=1; i<=n; i++) dp[i] = 0;
dpf(rt, -1);
vector<int> seq = dfs(rt, -1);
if(seq[0] != -1) {
cout << "YES\n";
cout << seq.size() * 2 << "\n";
for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
if(dp[rt] & 1) for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
else for(int i=seq.size()-1; i>=0; i--) cout << seq[i] << ' ';
cout << "\n"; return;
}
}
}
cout << "NO\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
newspapers.cpp: In function 'std::vector<int> dfs(int, int)':
newspapers.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i=0; i+1<vt.size(); i++) {
| ~~~^~~~~~~~~~
newspapers.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(!(prv == -1 && i+2 == vt.size()))res.push_back(node);
| ~~~~^~~~~~~~~~~~
newspapers.cpp: In function 'void solve(int)':
newspapers.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
| ~^~~~~~~~~~~
newspapers.cpp:91:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(dp[rt] & 1) for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
