#include <bits/stdc++.h>
using namespace std;
using tii = tuple<int,int,int>;
using pii = pair<int,int>;
const int inf = 1e6 + 5, 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;
ondiam[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(node == -1)
return;
if(state == 0) {
commence(heavy[node], 0);
rez.push_back(node);
for(auto x : light[node])
//cerr << x << ' ' << node << ' ',
rez.push_back(x),
rez.push_back(node);
if(node != l)
return;
if(light[node].size())
rez.pop_back();
commence(node, 1);
return;
}
if(state == 1) {
if(node != l || light[node].size() == 0)
rez.push_back(node);
for(auto x : light[node])
//cerr << x << ' ' << node << ' ',
rez.push_back(x),
rez.push_back(node);
commence(heavy[node], 1);
return;
}
}
pii findend(int node, int f) {
int cnt = 0;
for(auto x : g[node]) {
if(x == f) continue;
if(h[x] > 2)
cnt++;
}
if(cnt >= 2)
return {-1, inf};
cnt = 0;
for(auto x : g[node]) {
if(x == f) continue;
if(h[x] > 1)
cnt++;
}
if(cnt == 0)
return {node, 1};
for(auto x : g[node]) {
if(x == f)
continue;
if(h[x] > 1) {
auto tmp = findend(x, node);
tmp.second++;
return tmp;
}
}
}
int main() {
int n, m;
cin >> n >> m;
if(n == 1) {
cout << "YES\n1\n1\n";
return 0;
}
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;
}
}
}
}
for(int i = 1; i <= n; i++)
ondiam[i] = 0;
int mn = len, mnl = l, mnr = r;
for(int i = 1; i <= n; i++) {
finddiam(i, i);
tie(r, len) = findend(i, i);
//cerr << i << ": " << r << ' ' << len << '\n';
if(len < mn) {
mn = len;
mnl = i;
mnr = r;
}
//cerr << mnl << ": " << mnr << ' ' << mn << '\n';
}
tie(l, r, len ) = tii{mnl, mnr, mn};
markdiam(l, l, r);
finddiam(l, l);
for(int i = 1; i <= n; i++) {
if(ondiam[i] == 1) {
//cerr << "ceva\n";
for(auto x : g[i]) {
if(ondiam[x])
continue;
if(h[x] > 2) {
cout << "NO\n";
return 0;
}
cerr << i << ' ' << x << ' ' << h[x] << '\n';
if(h[x] == 2) {
light[i].push_back(x);
}
}
}
}
if(len == 1 && light[l].size() == 0) {
cerr << "amog\n";
cout << "YES\n2\n" << l << ' ' << r << '\n';
return 0;
}
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
Compilation message
newspapers.cpp: In function 'pii findend(int, int)':
newspapers.cpp:122:1: warning: control reaches end of non-void function [-Wreturn-type]
122 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
