You are an agent working behind the scenes in world history, dedicated to the goal of achieving world peace. In the world, there are N countries, numbered from 1 to N. Your ultimate goal is to achieve as many friendly relationships between the countries as possible. In order to help plan your actions, you drew a diagram of the current state of the international relations.
You prepared a large sheet of drawing paper and drew N dots representing each of the countries. Next, you drew M arrows between the countries, representing the current international relations. An arrow from country a to country b means that country a has sent ambassadors to country b. From now on, we will refer to an arrow pointing from country a to country b as arrow(a, b).
To help kickstart friendly relations between countries, we will consider treaty meetings between countries. We will call these treaty meetings conferences from now on. In order for two countries p and q to hold a conference, it is necessary for both countries to have an ambassador from the same country. After each conference, both countries will each send an ambassador to the other country. In other words, if we want to hold a conference between country p and country q, arrow(x, p) and arrow(x, q) must exist for some mediating country x. After the conference is held, there will be two new arrows arrow(p, q) and arrow(q, p), if they did not already exist.
For each pair of countries, your job is to pick the intermediary country such that they will be able to hold a conference. In order to perform your job as well as possible, you have decided to run a simulation of your choices on the paper. As your ultimate goal is world peace, you want to know the maximum number of arrows you can eventually draw on the paper if you repeating the process of holding conferences between pairs of countries, choosing pairs of countries optimally.
Given the number of countries and all the current international relationships between countries, find the maximum number of arrows you can eventually draw on the paper if you choose your conferences optimally.
Read from standard input.
- On the first line, there are two integers, N and M. N represents the number of countries in the world and M represents the current number of international relationships between countries.
- On ith line of the next M lines, there are two integers, Ai and Bi. This means that there is an arrow from country Ai to country Bi. In other words, country Ai has sent an ambassador to country Bi.
Print a single integer on a single line to standard output. The integer should be the maximum number of arrows you can eventually draw on the paper. Note that you have to include both the newly-drawn arrows in your simulation and the arrows that you have already drawn on the paper.
All the testcases satisfy the following constraints.
- 1 ≤ N ≤ 100 000.
- 0 ≤ M ≤ 200 000.
- 1 ≤ Ai ≤ N (1 ≤ i ≤ M).
- 1 ≤ Bi ≤ N (1 ≤ i ≤ M).
- Ai ≠ Bi (1 ≤ i ≤ M).
- (Ai, Bi) ≠ (Aj, Bj) (1 ≤ i < j ≤ M).
Subtask 1 (5 points):
Subtask 2 (30 points):
Subtask 3 (65 points):
No further constraints.
Sample Input 1
Sample Output 1
If you take the following actions, you can draw 10 arrows in total.
- With country 1 as intermediary, hold a conference between countries 2 and 3.
- With country 4 as intermediary, hold a conference between countries 3 and 5.
- With country 3 as intermediary, hold a conference between countries 2 and 5.