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 std::vector;
using std::array;
using std::pair;
using std::tuple;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
if (M != N - 1) {
std::cout << "NO\n";
return 0;
}
if (N == 1) {
std::cout << "YES\n1\n1\n";
return 0;
}
vector<vector<int>> graph(N);
for (int i = 0; i < M; ++i) {
int a, b;
std::cin >> a >> b;
a -= 1, b -= 1;
graph[a].push_back(b);
graph[b].push_back(a);
}
const auto bfs = [&](const int src) {
vector<int> dist(N, -1);
std::queue<int> que;
const auto push = [&](const int u, const int d) {
if (dist[u] == -1) {
dist[u] = d;
que.push(u);
}
};
push(src, 0);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (const int v : graph[u]) {
push(v, dist[u] + 1);
}
}
return dist;
};
const auto dist0 = bfs(0);
const int L = std::max_element(dist0.begin(), dist0.end()) - dist0.begin();
const auto distL = bfs(L);
const int R = std::max_element(distL.begin(), distL.end()) - distL.begin();
const int D = distL[R];
const auto distR = bfs(R);
vector<int> path(D + 1);
for (int i = 0; i < N; ++i) {
if (distL[i] + distR[i] > D + 4) {
std::cout << "NO\n";
return 0;
}
if (distL[i] + distR[i] == D) {
path[distL[i]] = i;
}
}
if (D <= 2) {
const int cen = path[D / 2] + 1;
std::cout << "YES\n2\n";
std::cout << cen << ' ' << cen << '\n';
return 0;
}
vector<int> ans;
for (int i = 1; i < D; ++i) {
const int u = path[i];
ans.push_back(u);
for (const int v : graph[u]) {
if (graph[v].size() > 1 and distL[v] + distR[v] > D) {
ans.push_back(v);
ans.push_back(u);
}
}
}
for (int i = D - 1; i > 0; --i) {
const int u = path[i];
ans.push_back(u);
for (const int v : graph[u]) {
if (graph[v].size() > 1 and distL[v] + distR[v] > D) {
ans.push_back(v);
ans.push_back(u);
}
}
}
std::cout << "YES\n";
const int n = ans.size();
std::cout << n << '\n';
for (int i = 0; i < n; ++i) {
std::cout << ans[i] + 1 << " \n"[i + 1 == n];
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |