Problem J
Just Enough Bridges

Chimera Ant is an intelligent and hard-working species.

There is a colony of $n$ Chimera Ants living near Han River in Danang, Vietnam. They have built $n$ houses (one house for one ant) on one side of Han River, and $n$ feeding grounds on the other side of Han River. The houses are numbered from $1$ to $n$, and the feeding grounds are also numbered from $1$ to $n$.

The ants have also built $m$ bridges across Han River $(m \ge n)$, each bridge connects one house to one feeding ground. It is possible that there are more than one bridge connecting a house and a feeding ground.

Every morning, the $n$ ants select $n$ bridges, to go to from their houses to their feeding grounds.

The bridges were built in such a way that it is possible for the ants to go directly to all $n$ feeding grounds. In other words, there exist a permutation $P$ of all integers from $1$ to $n$, such that there exists a bridge connecting the $i$-th house with the $P_ i$-th feeding ground.

The ants feel that they have built too many bridges. Thus they want to remove exactly one bridge, so that the above condition is still true.

Even though the Chimera Ants are very intelligent, they are not good with numbers. Please help the ants figure out how many different bridges they can remove.


The first line of the input contains two integers $n$ and $m$ $(1 \le n \le m \le 10^5)$.

Each of the next $m$ lines contains two integers $u$ and $v$ $(1 \le u, v \le n)$ — indicating that there is a bridge between the $u$-th house and the $v$-th feeding ground. Note that there may be multiple bridges between the same $u$ and $v$, and they are considered different.


The number of bridges satisfying the given conditions.

Sample Input 1 Sample Output 1
2 3
1 1
1 2
2 2

Please log in to submit a solution to this problem

Log in