Description

你知道 Just Odd Inventions 社吗? 这个公司的业务是 “只不过是奇妙的发明”. 这里简称为 JOI 社.

JOI 社的某个实验室中有着复杂的电路. 电路由 \(n\) 个节点和 \(m\) 根细长的电阻组成. 节点被标号为 \(1 - n\);

每个节点有一个可设定的状态【高电压】或者【低电压】. 每个电阻连接两个节点, 只有 一端是高电压, 另一端是低电压的电阻才会有电流流过. 两端都是高电压或者低电压的电阻不会有电流流过.

某天, JOI 社为了维护电路, 选择了一根电阻, 为了能让【只有这根电阻上的电流停止流动, 其他 \(m - 1\) 根电阻中都有电流流过】, 需要调节各节点的电压. 为了满足这个条件, 能选择的电阻共有多少根?

对了, JOI 社这个奇妙的电路是用在什么样的发明上的呢? 这是公司内的最高机密, 除了社长 以外谁都不知道哦~

现在给出电路的信息, 请你输出电路维护时可以选择使其不流的电阻的个数.

Input

第一行两个空格分隔的正整数 \(n, m\), 表示电路中有 \(n\) 个节点和 \(m\) 根电阻.

接下来 \(m\) 行, 第 \(i\) 行有两个空格分隔的正整数 \(A_i, B_i (1 \leq A_i, B_i \leq n, A_i \neq B_i)\), 表示第 \(i\) 个电阻连接节点 \(A_i\) 和节点 \(B_i\).

Output

输出一行一个整数, 代表电路维护时可选择的使其不流的电阻个数.

Sample Input

4 4
1 2
2 3
3 2
4 3

Sample Output

2

Data Range

对于所有数据, 保证:\(2 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5\), 但是不保证图是连通的, 也不保证没有重边.

Explanation

题目好复杂......

简化来说就是这样一道题, 给定一个不一定联通的无向图, 求将节点黑白染色以后, 有多少种情况下只有一条边两边颜色相同, 其他边两边颜色不同?

PoPoQQQ 给了这样一种解法, 说只要求出生成树就可以了......

因为没有什么太大关系, 所以随便一个生成树就可以了...... 然后树上距离为奇数的一定是可以颜色互异的, 距离为偶数的颜色一定相同...... 然后统计一下就可以了.

dfs(i, NULL) 给写成 dfs(1, NULL) 我也是醉了......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 200100, maxm = 500100;

class TreeManager
{
public:
    struct edge {
        int u, v;
        edge *next, *rev;
    };
    int n, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->rev = q;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->rev = p;
        q->next = edges[v]; edges[v] = q;
        return ;
    }
    bool vis[maxn];
    int depth[maxn], par[maxn];
    int good[maxn], bad[maxn];
    int good_cnt, bad_cnt;
    void dfs(int p, edge *from)
    {
        vis[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->rev != from) {
                if (!vis[ep->v]) {
                    par[ep->v] = p;
                    depth[ep->v] = depth[p] + 1;
                    dfs(ep->v, ep);
                    good[p] += good[ep->v];
                    bad[p] += bad[ep->v];
                } else {
                    if (depth[ep->v] > depth[p])
                        continue;
                    if ((depth[p] - depth[ep->v]) % 2 == 1)
                        good[p]++, good[ep->v]--, good_cnt++;
                    else
                        bad[p]++, bad[ep->v]--, bad_cnt++;
                }
            }
        return ;
    }
    int work(void)
    {
        for (int i = 1; i <= n; i++)
            if (!vis[i]) {
                depth[i] = 1;
                par[i] = 0;
                dfs(i, NULL);
            }
        // Processing results
        int res = 0;
        for (int i = 1; i <= n; i++)
            if (par[i] && bad[i] == bad_cnt && !good[i])
                res += 1;
        if (bad_cnt == 1)
            res += 1;
        return res;
    }
} graph;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n;
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        graph.add_edge(a, b);
    }
    int res = graph.work();
    printf("%d\n", res);
    return 0;
}