This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"
#include "../Utility/template.hpp"
#include "../Algorithm/maximum_independent_set.hpp"
int main() {
int n, m;
cin >> n >> m;
vec<vec<int>> ng(n, vec<int>(n, 0));
rep(i, 0, m) {
int u, v;
cin >> u >> v;
ng[u][v] = 1;
ng[v][u] = 1;
}
auto res = maximum_independent_set(ng);
cout << res.size() << endl;
for(int x : res) cout << x << " ";
cout << endl;
}
#line 1 "verify/maximum_independent_set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)
#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
return x < y ? (x = y, true) : false;
}
struct io_setup {
io_setup() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} io_setup;
/*
@brief verify用テンプレート
*/
#line 1 "Algorithm/maximum_independent_set.hpp"
vec<int> maximum_independent_set(vec<vec<int>> &ngs) {
int n = ngs.size();
int sl = n/2;
int sr = n - sl;
vec<ll> ng(n, 0);
rep(i, 0, n) rep(j, 0, n) if(ngs[i][j]) {
ng[i] |= 1LL << j;
}
vec<int> dp,pre,self,dp2,pre2,self2;
dp = pre = self = vec<int>(1LL << sl, 0);
dp2 = pre2 = self2 = vec<int>(1LL << sr, 0);
self = vec<int>(1LL << sl, -1);
self2 = vec<int>(1LL << sr, -1);
rep(s, 1, 1LL << sl) {
rep(i, 0, sl) if(s >> i & 1) {
ll ns = s ^ (1LL << i);
if(chmax(dp[s], dp[ns])) {
pre[s] = ns;
self[s] = -1;
}
ns = ns & (ns ^ ng[i]);
if(chmax(dp[s], dp[ns] + 1)) {
pre[s] = ns;
self[s] = i;
}
}
}
rep(s, 1, 1LL << sr) {
rep(i, 0, sr) if(s >> i & 1) {
ll ns = s ^ (1LL << i);
if(chmax(dp2[s], dp2[ns])) {
pre2[s] = ns;
self2[s] = -1;
}
ns = ns & (ns ^ (ng[i + sl] >> sl));
if(chmax(dp2[s], dp2[ns] + 1)) {
pre2[s] = ns;
self2[s] = i + sl;
}
}
}
int sz = -1;
vec<ll> id(2, 0);
vec<int> res;
rep(s, 0, 1LL << sl) {
ll out = 0;
rep(i, 0, sl) if(s >> i & 1) out |= ng[i];
ll ns = (((1LL << n) - 1) ^ out) >> sl;
if(chmax(sz, dp[s] + dp2[ns])) {
id[0] = s;
id[1] = ns;
}
}
while(id[0] != 0) {
if(self[id[0]] != -1) res.push_back(self[id[0]]);
id[0] = pre[id[0]];
}
while(id[1] != 0) {
if(self2[id[1]] != -1) res.push_back(self2[id[1]]);
id[1] = pre2[id[1]];
}
return res;
}
/*
@brief 最大独立集合
*/
#line 4 "verify/maximum_independent_set.test.cpp"
int main() {
int n, m;
cin >> n >> m;
vec<vec<int>> ng(n, vec<int>(n, 0));
rep(i, 0, m) {
int u, v;
cin >> u >> v;
ng[u][v] = 1;
ng[v][u] = 1;
}
auto res = maximum_independent_set(ng);
cout << res.size() << endl;
for(int x : res) cout << x << " ";
cout << endl;
}