410065: GYM103934 M Egyptian municipal elections

The Egyptian government is organizing the municipal elections throughout the country. Currently, the two main political forces are the Sadat Democratic party and the Republican People's party. Both are making preparations to assure their victory in the upcoming elections. Both parties consider dangerous exchanging messages through internet. For that reason, they will use the Egyptian mailing system instead. To distinguish their messages, each party will put a mark on the message.

Since information is a key asset in any political campaign, both parties have infiltrated personnel in each mailing office of Egypt. To disrupt the communication of the opposition, when a mail passes through a post office, the personnel will exchange the mark in the message. That is, if a message has the mark of the Democrats, it will be exchanged for the mark of the Republicans, and vice-versa. We observe that, this exchange does not happen in the origin office or in the destination office. When sending a mail from office $$$A$$$ to office $$$B$$$, we do not know which offices the message will pass through. However, we know that a message will not pass through the same post office more than once.

The Democrats have hired Marcel "the optimizer" Saito to study the Egyptian mailing system. The Democrats want to know how many pairs of post offices are insecure and how many pairs of post offices are secure. We consider two distinct offices $$$A$$$ and $$$B$$$ secure (resp. insecure) if, regardless of the route a message takes from $$$A$$$ to $$$B$$$, the message arrives with the initial mark (resp. with the opposite mark).

As Marcel is always busy, he asks your help to answer this question.

The first line contains two integers, $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$M$$$ ($$$1 \leq M \leq 10^6$$$), the number of post offices in Egypt and the number of direct routes between post offices, respectively. In this problem, each post office is represented by an integer from $$$1$$$ to $$$N$$$. Each of the following $$$M$$$ lines contain two integers, say $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq N$$$, $$$X \neq Y$$$), indicating that we can send messages directly between the post offices $$$X$$$ and $$$Y$$$.

Two integers $$$R$$$ and $$$D$$$, the number of insecure pairs and the number of secure pairs, respectively.

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

4 6

5 3
1 2
1 3
1 4

3 3