#include <bits/stdc++.h>
using namespace std;
using tii = tuple<int,int,int>;
const int nmax = 1e3 + 5;
vector<int> g[nmax], light[nmax];
int h[nmax], atrleaf[nmax], heavy[nmax];
int ondiam[nmax];
void chmax(tii &l, tii r) {
l = max(l, r);
}
tii finddiam(int node, int f) {
tii rez = {1, node, node};
atrleaf[node] = node;
h[node] = 1;
for(auto x : g[node]) {
if(x == f) continue;
chmax(rez, finddiam(x, node));
if(h[x] + 1 > h[node]) {
h[node] = h[x] + 1;
atrleaf[node] = atrleaf[x];
}
}
int other = 0, atr = node;
for(auto x : g[node]) {
if(x == f || atrleaf[node] == atrleaf[x])
continue;
if(h[x] > other) {
other = h[x];
atr = atrleaf[x];
}
}
chmax(rez, tii{other + h[node], atrleaf[node], atr});
return rez;
}
static bool markdiam(int node, int f, int rez) {
if(node == rez) {
heavy[node] = -1;
return 1;
}
ondiam[node] = 1;
for(auto x : g[node]) {
if(x == f)
continue;
if(markdiam(x, node, rez)) {
heavy[node] = x;
return 1;
}
}
ondiam[node] = 0;
return 0;
}
vector<int> rez;
int len, l, r;
void commence(int node, bool state = 0) {
if(heavy[node] == -1)
return;
if(state == 0) {
commence(heavy[node], 0);
rez.push_back(node);
for(auto x : light[node])
rez.push_back(x),
rez.push_back(node);
if(node != l)
return;
commence(node, 1);
return;
}
if(state == 1) {
rez.push_back(node);
for(auto x : light[node])
rez.push_back(x),
rez.push_back(node);
commence(heavy[node], 1);
return;
}
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 0, x, y; i < m; i++) {
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
if(m >= n) {
cout << "NO\n";
return 0;
}
tie(len, l, r) = finddiam(1, 1);
markdiam(l, l, r);
finddiam(l, l);
for(int i = 1; i <= n; i++) {
if(ondiam[i] == 1) {
for(auto x : g[i]) {
if(ondiam[x])
continue;
if(h[x] > 2) {
cout << "NO\n";
return 0;
}
if(h[x] == 2)
light[i].push_back(x);
}
}
}
commence(l);
//cerr << l << ' ' << r<< '\n';
cout << "YES\n" << rez.size() << '\n';
for(auto x : rez)
cout << x<< ' ';
cout << '\n';
}
//4 1 6 1 2 3 3 2 1 6 1 4
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Integer parameter [name=k] equals to 0, violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Integer parameter [name=k] equals to 0, violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Integer parameter [name=k] equals to 0, violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
