给定一个 N 个点，M 条边的无向图，求问有多少对还未经连接的点对满足在连接它们后，该图为一个二分图.
注意这里点对 (u,v) 和点对 (v,u) 是同一对点对。
数据保证没有自环与重边。
输入格式
第一行两个数N,M,接下来M行，每行两个数 (u,v)，表示一条无向边。
输出格式
一个整数，表示选择方案总数。
样例 #1
样例输入 #1
5 4
4 2
3 1
5 2
3 2
样例输出 #1
2
样例 #2
样例输入 #2
4 3
3 1
3 2
1 2
样例输出 #2
0
样例 #3
样例输入 #3
9 11
4 9
9 1
8 2
8 3
9 2
8 4
6 7
4 6
7 5
4 5
7 8
样例输出 #3
9
数据范围
# C:Joty and Chocolate
## 题面翻译
Joty 有 $n$ 块瓷砖，编号为 $1,2,3,\cdots ,n$ ，Joty 可以把编号为 $a$ 的倍数的瓷砖刷成红色，同时她会得到 $p$ 块巧克力；她也可以把编号为 $b$ 的倍数的瓷砖刷成蓝色，同时她会得到 $q$ 块巧克力；**如果这个瓷砖是 $a,b$ 的公倍 数，则她可以任选一个颜色并得到对应的巧克力报酬，也只能选择一种**，并得到 对应的$p$或$q$ 块巧克力。
输入一行5个数据，$n,a,b,p,q$ 。
输出一个数据：表示 Joty 能得到的巧克力最多有多少？
## 输入格式
The only line contains five integers $ n $ , $ a $ , $ b $ , $ p $ and $ q $ ( ).
## 输出格式
Print the only integer $ s $ — the maximum number of chocolates Joty can get.
Note that the answer can be too large, so you should use $ 64 $ -bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.
## 样例 #1
### 样例输入 #1
```
5 2 3 12 15
```
### 样例输出 #1
```
39
```
## 样例 #2
### 样例输入 #2
```
20 2 3 3 5
```
### 样例输出 #2
```
51
```
## 数据范围
$100\%$的数据范围:$Y\leq 100,000$ 1<=n,a,b,p,q<=10^{9}
The rules of Sith Tournament are well known to everyone. n Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive.
Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.
输入格式
The first line contains a single integer n ( 1<=n<=18 ) — the number of participants of the Sith Tournament.
Each of the next n lines contains n real numbers, which form a matrix p_{ij} ( 0<=p_{ij}<=1 ). Each its element p_{ij} is the probability that the i -th participant defeats the j -th in a duel.
The elements on the main diagonal p_{ii} are equal to zero. For all different i , j the equality p_{ij}+p_{ji}=1 holds. All probabilities are given with no more than six decimal places.
Jedi Ivan is the number 1 in the list of the participants.
输出格式
Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed 10^{-6} .