This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
int n, m;
cin >> n >> m;
if (n == 1) {
cout << "YES\n";
cout << "1\n";
cout << "1\n";
return 0;
}
if (n == 2) {
cout << "YES\n";
cout << "2\n";
cout << "1 1\n";
return 0;
}
if (m >= n) {
cout << "NO\n";
return 0;
}
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> dep(n);
pair<int, int> mx{-1, -1};
function<void(int, int)> dfs = [&](int u, int p) {
mx = max(mx, pair(dep[u], u));
for (int v : adj[u]) {
if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
};
dfs(0, -1);
int last = mx.second;
mx = {-1, -1};
dep[last] = 0;
dfs(last, -1);
int u = mx.second;
vector<int> g;
function<bool(int, int)> dfs2 = [&](int u, int p) {
if (u == last) {
g.push_back(u);
return true;
}
for (int v : adj[u]) {
if (v != p && dfs2(v, u)) {
g.push_back(u);
return true;
}
}
return false;
};
dfs2(u, -1);
u = g[g.size() / 2];
vector<int> mxdep(n), par(n);
dfs = [&](int u, int p) {
par[u] = p;
mxdep[u] = u;
for (int v : adj[u]) {
if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
if (dep[mxdep[v]] > dep[mxdep[u]]) {
mxdep[u] = mxdep[v];
}
}
}
};
dep[u] = 0;
dfs(u, -1);
int cnt = 0;
for (int u = 0; u < n; u++) {
sort(adj[u].begin(), adj[u].end(), [&](int i, int j) {
return dep[mxdep[i]] < dep[mxdep[j]];
});
}
for (int v : adj[u]) {
if (dep[mxdep[v]] >= 3) {
cnt++;
}
}
if (cnt >= 3) {
std::cout << "NO\n";
return 0;
}
for (int i = 0; i < n; i++) {
if (i != u) {
int c = 0;
for (int v : adj[i]) {
if (dep[mxdep[v]] - dep[i] >= 3) {
c++;
}
}
if (c >= 2) {
cout << "NO\n";
return 0;
}
}
}
std::vector<int> a;
int s = -1;
dfs = [&](int u, int p) {
for (int v : adj[u]) {
if (v != p && adj[v].size() > 1) {
dfs(v, u);
}
}
if (s == -1) {
s = u;
}
};
dfs(u, -1);
int lst = -1;
dfs = [&](int u, int p) {
a.push_back(u);
lst = u;
for (int v : adj[u]) {
if (v != p && adj[v].size() > 1) {
dfs(v, u);
a.push_back(u);
}
}
};
dfs(s, -1);
while (a.back() != lst)
a.pop_back();
cout << "YES\n";
cout << 2 * a.size() << "\n";
for (int x : a) {
cout << x + 1 << " ";
}
reverse(a.begin(), a.end());
for (int x : a) {
cout << x + 1 << " ";
}
cout << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |