oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

friends_joi Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

friends_joi.html

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.

Input

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.

Output

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.

Constraints

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).

Subtasks

Subtask 1 (5 points):

  • N ≤ 100 is satisfied.

Subtask 2 (30 points):

  • N ≤ 5000 is satisfied.

Subtask 3 (65 points):

No further constraints.

Sample Input 1

5 4
1 2
1 3
4 3
4 5

Sample Output 1

10

Explanation

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.

Tags

JOI 2013/2014

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
15181s256MBMinimum
230281s256MBMinimum
365371s256MBMinimum
4011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o friends_joi -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.