1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 1E5 + 100;
vector<int> G[N];
int nn;
struct E { int to, nxt; };
namespace C {
E e[N];
int hd[N], ecnt;
void addedge(int u, int v) {
e[ecnt] = {v, hd[u]};
hd[u] = ecnt++;
}
int idx[N], clk, fa[N];
bool ring[N];
void init() { ecnt = 0; memset(hd, -1, sizeof hd); clk = 0; }
void dfs(int u, int feid) {
idx[u] = ++clk;
for (int i = hd[u]; ~i; i = e[i].nxt) {
if ((i ^ feid) == 1) continue;
int v = e[i].to;
if (!idx[v]) {
fa[v] = u; ring[u] = false;
dfs(v, i);
if (!ring[u]) { G[u].push_back(v); G[v].push_back(u); }
} else if (idx[v] < idx[u]) {
++nn;
G[nn].push_back(v); G[v].push_back(nn); // trick!
for (int x = u; x != v; x = fa[x]) {
ring[x] = true;
G[nn].push_back(x); G[x].push_back(nn);
}
ring[v] = true;
}
}
}
}
int f[N][2];
int n, m;
void dfs(int u, int fa) {
if (u <= n) {
f[u][0] = 0; f[u][1] = 1;
for (int& v: G[u]) {
if (v == fa) continue;
dfs(v, u);
if (v > n) continue;
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
} else {
static int cir[N], p, g[N][2], INF = 1E9;
for (int& v: G[u]) if (v != fa) dfs(v, u);
p = 0; for (int& v: G[u]) cir[p++] = v;
auto dp = [&]() {
FOR (i, 1, p) {
g[i][1] = f[cir[i]][1] + g[i - 1][0];
g[i][0] = f[cir[i]][0] + max(g[i - 1][0], g[i - 1][1]);
}
};
g[0][0] = f[cir[0]][0]; g[0][1] = -INF;
dp(); int g_0 = max(g[p - 1][0], g[p - 1][1]);
g[0][0] = -INF; g[0][1] = f[cir[0]][1];
dp(); int g_1 = g[p - 1][0];
f[fa][0] = g_0; f[fa][1] = g_1;
}
}
int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
cin >> n >> m; nn = n;
C::init();
FOR (_, 0, m) {
int u, v; scanf("%d%d", &u, &v);
C::addedge(u, v); C::addedge(v, u);
}
C::dfs(1, -1);
dfs(1, -1);
cout << max(f[1][0], f[1][1]) << endl;
}
|