#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 998244353;
int main() {
ll n, m;
cin >> n >> m;
vector<vector<ll> > adj(n);
// vector<vector<ll> > adj2(n);
for (ll i = 0; i < m; i++) {
ll a, b;
cin >> a >> b;
a--;b--;
// adj[a].push_back(b);
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<ll > dp(1<<n, 0);
for (ll i = 1; i < (1 << n); i++) {
bool fail = false;
for (ll j = 0; j < n; j++) {
if ((1 << j) & i) {
for (auto val: adj[j]) if ((1 << val) & i) fail=true;
}
}
if (!fail) dp[i]=1;
}
for (ll i = 1; i < (1<<n); i++) {
assert(dp[i]!=0);
for (ll j = 0; j < n; j++) {
if ((1 << j) & i) continue;
bool fail = true;
for (auto val: adj[j]) if ((1 << val) & i) fail = false;
// if (fail) cout << i << j << endl;
// if (i == 2) cout << dp[(1 << j) ^ i] << ((1 << j) ^ i) << endl;
if (!fail) dp[(1 << j) ^ i] = ((dp[(1 << j) ^ i] + dp[i]))%MOD;
}
// cout << i << dp[i] << endl;
}
assert((m * dp[(1<<n)-1]) % 2 == 0);
cout << ((m * dp[(1<<n)-1])/2)%MOD << endl;
// DIDN'T WORK
// for (ll i = 0; i < n; i++) dp[(1 << i)] = {1, 0};
// for (ll i = 1; i < (1<<n); i++) {
// // cout << i << dp[i].first << dp[i].second << endl;
// for (ll ne = 0; ne < n; ne++) {
// if ((1 << ne) & i) continue;
// ll c = 0;
// for (auto val: adj[ne]) {
// if ((1 << val) & i) {
// c++;
// }
// }
// bool conn = false;
// for (auto val: adj2[ne]) if ((1<<val)&i)conn=true;
// // cout << (i^(1 << ne)) << dp[i].first << c << endl;
// if (!conn) continue;
// dp[i^(1 << ne)].second=((dp[i^(1 << ne)].second)%MOD+((dp[i].second)%MOD)+(dp[i].first*c)%MOD)%MOD;
// dp[i^(1 << ne)].first=(dp[i^(1 << ne)].first+dp[i].first)%MOD;
// // cout << i<<(ne) << dp[i^(1 << ne)].second << endl;
// }
// // cout << dp[]
// }
// ll ans = 1;
// vector<bool> v(n, false);
// for (ll i = 0; i < n; i++) {
// if (!v[i]) {
// ll current=0;
// v[i] = true;
// queue<ll> q;
// q.push(i);
// while (!q.empty()) {
// ll cur = q.front();
// q.pop();
// current|=(1<<cur);
// for (auto val: adj2[cur]) if (!v[val]) {
// q.push(val);v[val]=true;
// }
// }
// ans = (ans * dp[current].second)%MOD;
// }
// }
// cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
