图染色

给定一个有 $N$ 个节点和 $M$ 条边的无向图，节点编号为 １～ｎ

你需要将每个节点染成黑色或者白色两种颜色之一。接下来会根据节点的颜色来生成所有边的颜色。每条边连接两个节点，只有其中一个节点是黑色、另一个节点是白色时该边会被染成黑色，否则该边会被染成白色。

请你求出，有多少条边满足，存在一种对于节点染色的方案，使得只有这条边是白色，其它 M - 1M−1 条边都是黑色。

输入格式

第一行两个空格分隔的正整数$N,M$

接下来 M 行，第 i 行有两个空格分隔的正整数

$A_i ,B_i (A_i != B_i)$

不保证图是连通的，也不保证没有重边。

输出格式

一行一个整数，代表答案。

数据范围

对于所有测试数据，

$$ 2 ≤ N ≤ 10^5, 1 ≤ M ≤ 2 \times 10_5 2≤N≤10 $$

输出时每行末尾的多余空格，不影响答案正确性
要求使用「文件输入输出」的方式解题，输入文件为 coloring.in，输出文件为 coloring.out
样例输入1

样例输出1

样例解释1
只有第三条边满足条件，方案为:将节点 11 和 44 染成白色，节点 22 和 33 染成黑色(如下图，用虚线表示白色的边;下同)。

样例输入2

样例输出2

样例解释2
只有第一条或第四条边满足条件(如下图)。

样例输入3

样例输出3

code

//#define NoFile
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define FILENAME coloring
#define strdef(arg) #arg
#define strdef2(arg) strdef(arg)
#define INFILE strdef2(FILENAME.in)
#define OUTFILE strdef2(FILENAME.out)
#define asm asm
#define auto auto
#define bool bool
#define break break
#define case case
#define catch catch
#define char char
#define class class
#define const const
#define const_cast const_cast
#define continue continue
#define default default
#define delete delete
#define do do
#define double double
#define dynamic_cast dynamic_cast
#define else else
#define enum enum
#define explicit explicit
#define export export
#define extern extern
#define false false
#define float float
#define for for
#define friend friend
#define goto goto
#define if if
#define inline inline
#define int int
#define long long
#define mutable mutable
#define namespace namespace
#define new new
#define operator operator
#define private private
#define protected protected
#define public public
#define register register
#define reinterpret_cast reinterpret_cast
#define return return
#define short short
#define signed signed
#define sizeof sizeof
#define static static
#define static_cast static_cast
#define struct struct
#define switch switch
#define template template
#define this this
#define throw throw
#define true true
#define try try
#define typedef typedef
#define typeid typeid
#define typename typename
#define union union
#define unsigned unsigned
#define using using
#define virtual virtual
#define void void
#define volatile volatile
#define wchar_t wchar_t
#define std std
#define brokenpoems brokenpoems
using namespace std;
namespace io
{
    template <typename _tp>
    inline bool read(_tp& tp)
    {
        char ch = getchar(),opt = tp = 0;
        while(!isdigit(ch)) {
            if(EOF == ch)return true;
            opt |= ('-' == ch);
            ch = getchar();
        }
        while(isdigit(ch)) {
            tp = (tp << 1) + (tp << 3) + (ch ^ '0');
            ch = getchar();
        }
        if(opt)tp = -tp;
        return false;
    }
    template <typename _tp>
    inline void out(const _tp& tp)
    {
        if(tp < 0)putchar('-'),out(-tp);
        else (tp > 9) ? (out(tp / 10)) : ((void)NULL),putchar(tp % 10 + '0');
    }

}
namespace brokenpoems
{
    using namespace io;
    const int maxn = 1e5 + 7,maxm= 4e5 + 7;
    struct Map {
        int e_size,n,m,id,time;
        int head[maxn],col[maxn],low[maxn];
        int dfn[maxn],sum[maxn],dep[maxn];
        struct edge {
            int next,to;
            edge(int a = 0,int b = 0):next(a),to(b) {}
        } e[maxm];
        Map(){
            e_size=1;
        }
        inline void init() {
            read(n),read(m);
            int x,y;
            for(register int i = 1; i <= m; ++i) {
                read(x),read(y);
                add_edge(x,y);
                add_edge(y,x);
            }
        }
        inline void add_edge(int from,int to) {
            e[++e_size]=edge(head[from],to);
            head[from]=e_size;
        }
        bool check(int x) {
            bool flg = 0;
            for(register int i = head[x]; i; i=e[i].next) {
                if(!col[e[i].to]) {
                    col[e[i].to] = 3 - col[x];
                    flg |= check(e[i].to);
                } else {
                    flg |= col[e[i].to] == col[x];
                }
            }
            return flg;
        }
        void coloring() {
            id = 0;
            for(register int i = 1; i <= n; ++i) {
                if(!col[i]) {
                    col[i] = 1;
                    if(check(i)) {
                        if(!id) id = i;
                        else {
                            puts("0");
                            exit(0);
                        }
                    }
                }
            }
        }
        int tarjan(int x,int eid) {
            dfn[x] = low[x] = ++time;
            int res = 0;
            for(register int i = head[x]; i; i=e[i].next) {
                if(i == eid)continue;
                if(!dfn[e[i].to])res += tarjan(e[i].to,i ^ 1);
                low[x] = min(low[x],low[e[i].to]);
                if(low[e[i].to] > dfn[x])res++;
            }
            return res;
        }
        int dfs(int x,int eid) {
            int res = 0;
            dep[x] = dep[e[eid].to] + 1;
            for(register int i = head[x]; i ; i = e[i].next) {
                if(i != eid) {
                    if(!dep[e[i].to]) {
                        res += dfs(e[i].to,i ^ 1);
                        sum[x] += sum[e[i].to];
                    } else if(dep[e[i].to] < dep[x]) {
                        if((dep[x] - dep[e[i].to]) & 1) {
                            --sum[x];
                            ++sum[e[i].to];
                        } else {
                            ++sum[x];
                            --sum[e[i].to];
                            ++res;
                        }
                    }
                }
            }
            return res;
        }
        void Solve() {
            init();
            coloring();
            if(!id) {
                int cnt = 0;
                for(register int i = 1; i <= n; ++i)
                    if(!dfn[i])
                        cnt += tarjan(i,0);
                out(cnt);
                cout<< id <<endl;
            } else {
                int cnt = dfs(id,0),ans = 0;
                for(register int i = 1; i <= n; ++i) {
                    ans += sum[i] == cnt;
                }
                out(ans + (cnt == 1));
            //    cout<< id <<endl;
            }
        }
    } M;
    void main()
    {
        M.Solve();
    }
}

int main()
{
#ifndef NoFile
    freopen(INFILE,"r",stdin);
    freopen(OUTFILE,"w",stdout);
#endif
    brokenpoems::main();
}

$$ $$

图染色