409938: GYM103860 H Harie Programming Contest

During 9102 A.D., $$$n$$$ students work for Harie University Wearable Technology Lab (or WTLab in short). Each student is self-identified as being either a "Ninniku Homan" (NH) or a "Siege Guy" (SG).

Nikuniku wants to organize a new kind of programming contest among them, in which each team has two members – one NH and one SG. The students are not allowed to pick their teammates by themselves. Instead, they make proposals and let Nikuniku decide the final team. A proposal between student $$$x$$$ and $$$y$$$ means they are willing to work together. Since the penalty of being dishonest at WTLab is pretty high, it is guaranteed that the proposals are valid, i.e. either $$$x$$$ or $$$y$$$ is a Siege Guy, but not both. Nikuniku does not know who is NH or SG, though.

Nikuniku would like to arrange teams in a way that her contest has as many teams as possible. However, to keep the lab's critical infrastructure running, she has to reserve two students for emergency. The two reserved students, unfortunately, cannot participate in the contest.

But Nikuniku doesn't want to compromise – she still wants the same number of teams as if all $$$n$$$ students are participating. Nikuniku is wondering how many different ways of picking the two reserved students there are so that she doesn't need to make a compromise.

The first line contains two integers separated by a space $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) – the number of students, and $$$m$$$ ($$$0 \leq m \leq 2 \cdot 10^5$$$) – the number of proposals.

The next $$$m$$$ lines each contain two integers $$$x$$$ ($$$1 \leq x \leq n$$$) and $$$y$$$ ($$$1 \leq y \leq n, x \neq y$$$), meaning that there is a proposal between $$$x$$$ and $$$y$$$.

It is guaranteed that the proposals are unique, i.e. for any given $$$x$$$ and $$$y$$$, there is at most one proposal between them.

Output an integer in one line – the answer to Nikuniku's question.

6 4
1 2
1 3
4 5
4 6

4

6 6
1 2
1 3
1 4
1 5
2 6
3 6

5

5 4
1 2
2 3
3 4
4 5

0