#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
const int N = 1e3+3;
vector <int> graph[N], color(N);
int depth[N], furthest[N];
vector <int> diameter, order;
int df, vf, in_diameter[N];
void find_furthest(int v, int p, int dist) {
order.pb(v);
if (dist > df) {
df = dist;
vf = v;
diameter = order;
}
for (auto to : graph[v]) {
if (to == p) continue;
find_furthest(to, v, dist+1);
}
order.pop_back();
}
int dfs(int v, int p) {
int mx = depth[v];
for (auto to : graph[v]) {
if (to == p || in_diameter[to]) continue;
depth[to] = depth[v] + 1;
mx = max(mx, dfs(to, v));
}
furthest[v] = mx;
return mx;
}
void dfs3(int v, int p, int c) {
color[v] = c;
for (auto to : graph[v]) {
if (to == p) continue;
dfs3(to, v, 1-c);
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
graph[a].pb(b);
graph[b].pb(a);
}
if (m >= n) {
cout << "NO" << endl;
return;
}
find_furthest(1, 1, 0);
df = 0;
find_furthest(vf, vf, 0);
df = 0;
for (auto to : diameter) in_diameter[to] = 1;
for (int i = 0; i < sz(diameter); i++) {
auto to = diameter[i];
dfs(to, to);
if (furthest[to] >= 3 && i >= 3 && i <= n-4) {
df++;
}
}
if (df) {
cout << "NO" << endl;
return;
}
dfs3(1, 1, 1);
int forbidden, start = 1, forbidden_leaves = 0;
for (int i = 1; i <= n; i++) {
if (sz(graph[i]) == 1) {
start = graph[i][0];
forbidden = color[i];
break;
}
}
for (int i = 1; i <= n; i++) {
if (sz(graph[i]) == 1 && forbidden == color[i]) {
forbidden_leaves++;
}
}
set <int> visited;
vector <int> orderr;
//~ int add = 1;
function <void(int, int, int)> dfs2 = [&](int v, int p, int origin) {
//~ if (add) {
//~ visited.insert(v);
//~ orderr.pb(v);
//~ }
//~ if (sz(visited) == n-forbidden_leaves) {
//~ add = 0;
//~ }
//~ for (auto to : graph[v]) {
//~ if (to == p) continue;
//~ if (sz(graph[to]) == 1 && color[to] == forbidden) continue;
//~ dfs2(to, v);
//~ if (add) {
//~ visited.insert(v);
//~ orderr.pb(v);
//~ }
//~ }
if (origin != v) {
orderr.pb(v);
orderr.pb(origin);
}
for (auto to : graph[v]) {
if (to == p || in_diameter[to] || sz(graph[to]) == 1) continue;
dfs2(to, v, origin);
}
};
//~ dfs2(start, start);
for (int i = 1; i < sz(diameter)-1; i++) {
orderr.pb(diameter[i]);
orderr.pb(diameter[i]);
dfs2(diameter[i], diameter[i], diameter[i]);
}
cout << "YES" << endl;
if (n == 1) {
cout << 1;
return;
}
else if (n == 2) {
cout << "1 1";
return;
}
cout << sz(orderr)*2 << endl;
for (auto to : orderr) cout << to << ' ';
for (auto to : orderr) cout << to << ' ';
}
int main() {
do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
12 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 9
9 10
10 11
5 12
*/
Compilation message
newspapers.cpp: In function 'void solve()':
newspapers.cpp:91:20: warning: variable 'start' set but not used [-Wunused-but-set-variable]
91 | int forbidden, start = 1, forbidden_leaves = 0;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
