Codeforces Round #407 (Div. 2) D,E

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.

Input

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.

Output

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

Examples

input

output

input

output

input

2 2
1 1
1 2

output

Note

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[1000006],loop[1000006];
vector<int>v[1000006];
void dfs(int x){
    if(vis[x]) return ;
    vis[x]=1;
    for(int i=0;i<(int)v[x].size();i++){
        int y=v[x][i];
        dfs(y);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y,lp=0;
    memset(vis,0,sizeof(vis));
    for(int i=0;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=1;i<=n;i++)
        if(!v[i].empty()||loop[i]){
            dfs(i);break;
        }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&(!v[i].empty()||loop[i]))
            return 0*printf("0
");
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        int tmp=(int)v[i].size();
        ans+=1LL*tmp*(tmp-1)/2;//C(tmp,2)
    }
    ans+=(1LL*lp*(lp-1)/2+1LL*lp*(m-lp));
    return 0*printf("%I64d
",ans);
}

BFS

Sasha and Kolya decided to get drunk with Coke, again. This time they have k types of Coke. i-th type is characterised by its carbon dioxide concentration $\text{[math]}$ . Today, on the party in honour of Sergiy of Vancouver they decided to prepare a glass of Coke with carbon dioxide concentration $\text{[math]}$ . The drink should also be tasty, so the glass can contain only integer number of liters of each Coke type (some types can be not presented in the glass). Also, they want to minimize the total volume of Coke in the glass.

Carbon dioxide concentration is defined as the volume of carbone dioxide in the Coke divided by the total volume of Coke. When you mix two Cokes, the volume of carbon dioxide sums up, and the total volume of Coke sums up as well.

Help them, find the minimal natural number of liters needed to create a glass with carbon dioxide concentration $\text{[math]}$ . Assume that the friends have unlimited amount of each Coke type.

Input

The first line contains two integers n, k (0 ≤ n ≤ 1000, 1 ≤ k ≤ 106) — carbon dioxide concentration the friends want and the number of Coke types.

The second line contains k integers a1, a2, ..., ak (0 ≤ ai ≤ 1000) — carbon dioxide concentration of each type of Coke. Some Coke types can have same concentration.

Output

Print the minimal natural number of liter needed to prepare a glass with carbon dioxide concentration $\text{[math]}$ , or -1 if it is impossible.

Examples

input

400 4
100 300 450 500

output

input

50 2
100 25

output

Note

In the first sample case, we can achieve concentration $\text{[math]}$ using one liter of Coke of types $\text{[math]}$ and $\text{[math]}$ : $\text{[math]}$ .

In the second case, we can achieve concentration $\text{[math]}$ using two liters of $\text{[math]}$ type and one liter of $\text{[math]}$ type: $\text{[math]}$ .

题意：
有k个浓度的可乐s[1~k]/1000（浓度可能有相同的），每种无限多，和一个目标浓度n/1000，问最少用几升可以配出目标浓度的可乐。

代码：

初始值x置为0，用bfs算出x值再次等于0的步数就是最少需要几升。

//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000006];
map<int,int>mp;
int main()
{
    int n,k,x,cnt=0;
    queue<int>q;
    scanf("%d%d",&n,&k);
    for(int i=0;i<k;i++){
        scanf("%d",&x);
        a[cnt++]=x-n;
    }
    sort(a,a+cnt);
    cnt=unique(a,a+cnt)-a;
    q.push(0);
    while(!q.empty()){
        x=q.front();q.pop();
        for(int i=0;i<cnt;i++){
            int y=x+a[i];
            if(abs(y)>1001) continue;//剪枝
            if(y==0){
                return 0*printf("%d
",mp[x]+1);
            }
            if(!mp[y]){
                mp[y]=mp[x]+1;
                q.push(y);
            }
        }
    }
    return 0*printf("-1
");
}