//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], g[maxn];
int getdep(int n, int par) {
int ret = 1;
for (int v:adj[n]) {
if (v != par) {
ret = max(ret, getdep(v, n) + 1);
}
}
return ret;
}
bool path[maxn];
void getpath(int n, int par) {
path[n] = 1;
bool to = 0;
for (int v:g[n]) {
if (v != par && g[v].size() > 1) {
getpath(v, n);
to = 1;
break;
}
}
if (to == 0) {
for (int v:g[n]) {
if (v != par) {
getpath(v, n);
break;
}
}
}
}
vector<int> ans;
int last = 0;
void solve(int n, int par) {
ans.push_back(n);
last = n;
for (int v:g[n]) {
if (v != par && !path[v]) {
ans.push_back(v);
ans.push_back(n);
}
}
for (int v:g[n]) {
if (v != par && path[v]) {
solve(v, n);
}
}
}
int main() {
io
int n, m;
cin >> n >> m;
for (int i = 0;i < m;i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (m > n - 1) {
cout << "NO\n";
return 0;
}
vector<int> nodes;
for (int i = 1;i <= n;i++) {
int cnt = 0;
for (int v:adj[i]) {
if (getdep(v, i) >= 3) cnt++;
}
if (cnt > 2) {
cout << "NO\n";
return 0;
}
if (adj[i].size() > 1) {
nodes.push_back(i);
for (int v:adj[i]) {
if (adj[v].size() > 1) {
g[i].push_back(v);
}
}
}
}
cout << "YES\n";
if (nodes.size() == 0) {
ans.push_back(1);
if (n > 1) ans.push_back(1);
} else if (nodes.size() == 1) {
ans.push_back(nodes[0]);
ans.push_back(nodes[0]);
} else {
for (int i:nodes) {
if (g[i].size() == 1 && g[g[i][0]].size() == 2) {
getpath(i, 0);
solve(i, 0);
break;
}
}
solve(last, 0);
}
cout << ans.size() << "\n";
for (int i:ans) cout << i << " ";
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
0 ms |
340 KB |
Integer 0 violates the range [1, 7] |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Integer 0 violates the range [1, 4] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
0 ms |
340 KB |
Integer 0 violates the range [1, 7] |
| 7 |
Halted |
0 ms |
0 KB |
- |
