#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define endl '\n'
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 37
#endif
template <typename T>
void print(vector<T> v) {
const int n = v.size();
for(int i = 1; i < n; ++i) {
cout << i << " : " << v[i] << '\n';
}
}
inline void solve(){
int n, m;
cin >> n >> m;
if(m >= n) {
cout << "NO\n";
return;
}
vector<vector<int> > g(n + 1);
for(int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> v(n + 1, true);
vector<int> sol;
v[0] = false;
while((int)sol.size() <= 5 * n) {
int mx = 0;
for(int i = 1; i <= n; ++i) {
if(count_if(g[i].begin(), g[i].end(), [&](int to) { return v[to]; }) == 1) {
auto it = find_if(g[i].begin(), g[i].end(), [&](int to) { return v[to]; });
assert(it != g[i].end());
if(g[*it].size() > g[mx].size()) {
mx = *it;
}
}
}
if(mx == 0) {
for(int i = 1; i <= n; ++i) {
if(v[i] == 1 and g[i].size() > g[mx].size()) {
mx = i;
}
}
}
v[mx] = false;
sol.push_back(mx);
vector<int> nv(n + 1);
bool ok = false;
for(int i = 1; i <= n; ++i) {
for(int to : g[i]) {
nv[i] |= v[to];
}
ok |= (nv[i]);
}
v = nv;
if(!ok) {
break;
}
}
if((int)sol.size() > 5 * n) {
cout << "NO\n";
return;
}
cout << "YES\n" << sol.size() << "\n";
for(int x : sol) {
cout << x << ' ';
}
cout << endl;
}
signed main(){
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("err.txt", "w", stderr);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// signed t; cin >> t; while(t--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Integer 0 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Integer 0 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Integer 0 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
