Little boy Igor wants to become a traveller. At first, he decided to visit all the cities of his motherland — Uzhlyandia.

It is widely known that Uzhlyandia has n cities connected with m bidirectional roads. Also, there are no two roads in the country that connect the same pair of cities, but roads starting and ending in the same city can exist. Igor wants to plan his journey beforehand. Boy thinks a path is good if the path goes over m - 2 roads twice, and over the other 2 exactly once. The good path can start and finish in any city of Uzhlyandia.

Now he wants to know how many different good paths are in Uzhlyandia. Two paths are considered different if the sets of roads the paths goes over exactly once differ. Help Igor — calculate the number of good paths.

The first line contains two integers n, m (1 ≤ n, m ≤ 106) — the number of cities and roads in Uzhlyandia, respectively.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) that mean that there is road between cities u and v.

It is guaranteed that no road will be given in the input twice. That also means that for every city there is no more than one road that connects the city to itself.

Print out the only integer — the number of good paths in Uzhlyandia.

In first sample test case the good paths are:

• 2 → 1 → 3 → 1 → 4 → 1 → 5,
• 2 → 1 → 3 → 1 → 5 → 1 → 4,
• 2 → 1 → 4 → 1 → 5 → 1 → 3,
• 3 → 1 → 2 → 1 → 4 → 1 → 5,
• 3 → 1 → 2 → 1 → 5 → 1 → 4,
• 4 → 1 → 2 → 1 → 3 → 1 → 5.

There are good paths that are same with displayed above, because the sets of roads they pass over once are same:

• 2 → 1 → 4 → 1 → 3 → 1 → 5,
• 2 → 1 → 5 → 1 → 3 → 1 → 4,
• 2 → 1 → 5 → 1 → 4 → 1 → 3,
• 3 → 1 → 4 → 1 → 2 → 1 → 5,
• 3 → 1 → 5 → 1 → 2 → 1 → 4,
• 4 → 1 → 3 → 1 → 2 → 1 → 5,
• and all the paths in the other direction.

Thus, the answer is 6.

In the second test case, Igor simply can not walk by all the roads.

In the third case, Igor walks once over every road.

题意：

n个点，m条无向边，要求走遍所有的点并且其中有两条边走过一次，m-2条边走过两次，问方案数是多少。

代码：

//将每条无向边变成两条有向边，题目就变成了从2*m条边中去掉两条能够形成哈密顿图。

//可以选两条相邻的边（非自环）或者两条自环，或者一条自环和一条非自环边

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,m,vis[],loop[];

vector<int>v[];

void dfs(int x){

    if(vis[x]) return ;

    vis[x]=;

    for(int i=;i<(int)v[x].size();i++){

        int y=v[x][i];

        dfs(y);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    int x,y,lp=;

    memset(vis,,sizeof(vis));

    for(int i=;i<m;i++){

        scanf("%d%d",&x,&y);

        if(x==y) loop[x]++,lp++;

        else{

            v[x].push_back(y);

            v[y].push_back(x);

        }

    }

    for(int i=;i<=n;i++)

        if(!v[i].empty()||loop[i]){

            dfs(i);break;

        }

    for(int i=;i<=n;i++){

        if(!vis[i]&&(!v[i].empty()||loop[i]))

            return *printf("0\n");

    }

    ll ans=;

    for(int i=;i<=n;i++){

        int tmp=(int)v[i].size();

        ans+=1LL*tmp*(tmp-)/;//C(tmp,2)

    }

    ans+=(1LL*lp*(lp-)/+1LL*lp*(m-lp));

    return *printf("%I64d\n",ans);

}

BFS

400 4
100 300 450 500

2

50 2
100 25

3

//

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[];

map<int,int>mp;

int main()

{

    int n,k,x,cnt=;

    queue<int>q;

    scanf("%d%d",&n,&k);

    for(int i=;i<k;i++){

        scanf("%d",&x);

        a[cnt++]=x-n;

    }

    sort(a,a+cnt);

    cnt=unique(a,a+cnt)-a;

    q.push();

    while(!q.empty()){

        x=q.front();q.pop();

        for(int i=;i<cnt;i++){

            int y=x+a[i];

            if(abs(y)>) continue;//剪枝

            if(y==){

                return *printf("%d\n",mp[x]+);

            }

            if(!mp[y]){

                mp[y]=mp[x]+;

                q.push(y);

            }

        }

    }

    return *printf("-1\n");

}