#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<int> edge[200005];
int bridges = 0;
int par[400005];
int disc[200005];
int d = 0;
map<ii, int> ecount;
int find(int x)
{
if (par[x] == x)
return x;
return par[x] = find(par[x]);
}
void merge(int x, int y)
{
x = find(x);
y = find(y);
par[x] = y;
}
int bridge(int here, int par)
{
disc[here] = ++d;
int ret = disc[here];
int child = 0;
for (int there : edge[here])
{
if (there == par)
continue;
if (!disc[there])
{
int df = bridge(there, here);
if (df > disc[here] && ecount[{here, there}] == 1)
bridges++;
ret = min(ret, df);
}
else
{
ret = min(ret, disc[there]);
}
}
return ret;
}
void calcBridge(int n)
{
for (int i = 1; i <= n; i++)
if (!disc[i])
bridge(i, 0);
}
int visited[200005];
vector<int> oddCycle;
vector<pair<int, bool>> oddComp[400005];
bool odd(int root)
{
oddCycle.push_back(root);
for (auto& e : edge[root])
{
if (visited[e] == visited[root])
{
vector<int> trace = { e };
while (oddCycle.back() != e)
{
trace.push_back(oddCycle.back());
oddCycle.pop_back();
}
oddCycle = trace;
return true;
}
if (visited[e] != -1)
continue;
visited[e] = (visited[root] + 1) % 2;
if (odd(e))
return true;
}
oddCycle.pop_back();
return false;
}
void findOddCycle(int n)
{
memset(visited, -1, sizeof(visited));
for (int i = 1; i <= n; i++)
{
if (visited[i] != -1)
continue;
visited[i] = 0;
if (odd(i))
return;
}
}
set<ii> isOdd;
int color[200005];
void coloring(int n)
{
memset(color, -1, sizeof(color));
for (int i = 1; i <= n; i++)
{
if (color[i] != -1)
continue;
vector<int> comp;
queue<int> q;
color[i] = 0;
q.push(i);
while (!q.empty())
{
auto now = q.front();
comp.push_back(now);
q.pop();
for (auto& e : edge[now])
{
if (color[e] != -1 || isOdd.find({ now, e }) != isOdd.end())
continue;
color[e] = (color[now] + 1) % 2;
q.push(e);
}
}
for (int j = 0; j < comp.size() - 1; j++)
{
if (color[comp[j]] == color[comp[j + 1]])
{
merge(comp[j], comp[j + 1]);
merge(n + comp[j], n + comp[j + 1]);
}
else
{
merge(comp[j], n + comp[j + 1]);
merge(n + comp[j], comp[j + 1]);
}
}
}
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= 2 * n; i++)
par[i] = i;
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
ecount[{u, v}]++;
ecount[{v, u}]++;
}
calcBridge(n);
findOddCycle(n);
if (oddCycle.empty())
{
printf("%d\n", bridges);
return 0;
}
for (int i = 0; i < oddCycle.size(); i++)
{
int x = oddCycle[i];
int y = oddCycle[(i + 1) % oddCycle.size()];
isOdd.emplace(x, y);
isOdd.emplace(y, x);
}
coloring(n);
// odd cycle 제외한 위치에서 문제 있는지 확인
for (int i = 1; i <= n; i++)
{
for (auto& e : edge[i])
{
if (isOdd.find({ i,e }) != isOdd.end())
continue;
// odd cycle 하나 제거했는데도 여전히 같은 쌍이 나옴 => 불가능
if (find(i) == find(e))
{
printf("0\n");
return 0;
}
}
}
int total = 0;
vector<int> psum(oddCycle.size() + 1);
set<int> ps;
for (int i = 0; i < oddCycle.size(); i++)
{
int x = find(oddCycle[i]);
int y = find(oddCycle[i] + n);
ps.insert(x);
ps.insert(y);
oddComp[x].emplace_back(i, true);
oddComp[y].emplace_back(i, false);
}
for (auto& pi : ps)
{
if (oddComp[pi].size() == 1)
continue;
for (int i = 0; i < oddComp[pi].size(); i++)
{
auto a = oddComp[pi][i];
auto b = oddComp[pi][(i + 1) % oddComp[pi].size()];
int d = b.xx - a.xx;
if (d < 0)
d += oddCycle.size();
if ((a.yy == b.yy && d % 2 == 0) || (a.yy != b.yy && d % 2 == 1))
swap(a, b);
total++;
if (a.xx < b.xx)
{
psum[a.xx]++;
psum[b.xx]--;
}
else
{
psum[0]++;
psum[b.xx]--;
psum[a.xx]++;
}
}
}
for (int i = 1; i < oddCycle.size(); i++)
psum[i] += psum[i - 1];
int result = 0;
for (int i = 0; i < oddCycle.size(); i++)
{
int x = oddCycle[i];
int y = oddCycle[(i + 1) % oddCycle.size()];
if (ecount[{x, y}] > 1)
continue;
if (psum[i] == total)
result++;
}
printf("%d\n", result);
return 0;
}
