//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
const int N = 2e5 + 1, mod = 1e9 + 7;
const ll inf = 2e9;
double eps = 1e-15;
bool flg = 0;
vector<int> gr(N), st[1 << 20];
int n, m, was[1 << 20];
vector<int> f(int msk) {
if (was[msk]) return st[msk];
if (!msk) return {};
was[msk] = 1;
vector<int> ans(101);
st[msk] = ans;
vector<int> s;
for (int i = 0; i < n; i++) {
if (msk >> i & 1) {
s.push_back(i);
}
}
vector<int> pr(sz(s)), sf(sz(s));
for (int i = 0; i < sz(s); i++) {
if (i) pr[i] = pr[i - 1];
pr[i] |= gr[s[i]];
}
for (int i = sz(s) - 1; i >= 0; i--) {
if (i < sz(s) - 1) sf[i] = sf[i + 1];
sf[i] |= gr[s[i]];
}
for (int i = 0; i < sz(s); i++) {
int mask = 0;
if (i) mask |= pr[i - 1];
if (i < sz(s) - 1) mask |= sf[i + 1];
vector<int> x = f(mask);
x.push_back(s[i]);
if (sz(x) < sz(ans)) ans = x;
}
st[msk] = ans;
return ans;
}
void slv() {
cin >> n >> m;
if (m > n - 1) {
cout << "NO";
return;
}
vector<int> g[n];
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
if (n <= 1) {
for (int i = 0; i < n; i++) {
for (int to: g[i]) {
gr[i] |= (1 << to);
}
}
vector<int> ans = f((1 << n) - 1);
if (sz(ans) > 5 * n) cout << "NO\n";
else {
reverse(all(ans));
cout << "YES\n" << sz(ans) << '\n';
for (int x: ans) cout << x + 1 << ' ';
}
return;
}
vector<int> s, ans;
for (int i = 1; i <= n; i++) s.push_back(i);
for (int i = 1; i <= 10 * n && sz(s); i++) {
int pos = min(sz(s) - 1, 1);
ans.push_back(s[pos]);
vector<bool> is(n + 2);
for (int j = 0; j < sz(s); j++) {
if (j == pos) continue;
is[s[j] - 1] = is[s[j] + 1] = 1;
}
s.clear();
for (int i = 1; i <= n; i++) {
if (is[i]) s.push_back(i);
}
}
cout << "YES\n";
cout << (n - 2) * 2 << '\n';
for (int i = 2; i < n; i++) cout << i << ' ';
if (n & 1) {
for (int i = 2; i < n; i++) cout << i << ' ';
}else {
for (int i = n - 1; i >= 2; i--) cout << i << ' ';
}
}
main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int tp = 1;
if (flg) cin >> tp;
while (tp--) {
slv();
}
}
//wenomechainsama
Compilation message
newspapers.cpp:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
121 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
27740 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
27620 KB |
Integer parameter [name=k] equals to 0, violates the range [1, 10] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
27624 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
27740 KB |
Integer parameter [name=k] equals to 0, violates the range [1, 10] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
27740 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
27620 KB |
Integer parameter [name=k] equals to 0, violates the range [1, 10] |
| 3 |
Halted |
0 ms |
0 KB |
- |
