F - 友だちをつくろう 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MiB

配点 : 100 点

問題文

あなたは歴史の裏舞台で活躍するエージェントであり,世界の平和に向けて日々活動を続けている.この世界には N 個の国があり,それぞれ 1 から N までの異なる番号がふられている.これらの N 個の国々の間にできる限り友好な関係を築いてもらうことがあなたの目的である.あなたはエージェントの仕事の計画を立てるため,現在の国際関係を表す図を描いた.

あなたは大きな画用紙を一枚用意し,まずそこにそれぞれの国を表す N 個の点を打った.次に,現在の国際関係を表すために,2 つの国を結ぶ矢印を M 本描いた.国 a を表す点から別の国 b を表す点へと向かう矢印は,「現在,国 a が国 b に大使を派遣している」ということを表す.以下では,国 a を表す点から国 b を表す点へと向かう矢印を矢印 (a, b) と呼ぶ.こうして描いた N 個の点と M 本の矢印が現在の国際関係を表す図である.

国同士の友好関係のきっかけとして,2 国間での友好条約締結会議(以下では単に「会議」という)を行うことを考えよう.ある 2 つの国 p, q が会議を行うためには,両方の国に大使を派遣しているような国 x が仲介として必要である.そして,会議を行った後にそれぞれの国は相手国に大使を派遣する.すなわち,国 p と国 q が会議を行うためには,矢印 (x, p) と矢印 (x, q) があるような国 x が存在していなければならず,会議を行った後では矢印 (p, q) と矢印 (q, p) を新たに描き加える.ただし,矢印がすでに描かれている場合には新たに描き加えることはしない.

あなたの仕事は,会議を行うことができるような 2 つの国と,その会議の仲介となる国を選び,会議を行わせることである.図を使ってこの仕事のシミュレーションをするにあたって,世界がどれほど平和に近づいているかについて,画用紙の上の矢印の個数を基準に考えることにした.つまり,2 つの国を選んで会議を行わせるといったことを繰り返すことで,画用紙の上の矢印の個数を最大でいくつにできるかが知りたい.

課題

この世界にある国の個数と,現在の国際関係を示す情報が与えられたとき,2 つの国を選んで会議を行わせるといったことを繰り返すことで,画用紙の上の矢印の個数を最大でいくつにできるかを求めるプログラムを作成せよ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には整数 N, M が空白を区切りとして書かれている.N は画用紙上の点の個数(この世界にある国の個数),M は画用紙上の矢印の個数を表す.
  • 続く M 行には,画用紙上の矢印の情報がそれぞれ書かれている.このうちの i 行目 (1 \leqq i \leqq M) には 2 つの整数 A_{i}, B_{i} が空白を区切りとして書かれている.これは画用紙上に国 A_{i} を表す点から国 B_{i} を表す点へ向かう矢印が描かれていること,すなわち国 A_{i} が国 B_{i} へ大使を派遣していることを表す.

出力

標準出力に,実現できる矢印の個数の最大値を 1 行で出力せよ.矢印の個数には,会議によって新たに描き加えられたもののみでなく現在すでに描かれているものも数えることに注意せよ.

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq N \leqq 100\,000.
  • 0 \leqq M \leqq 200\,000.
  • 1 \leqq A_{i} \leqq N (1 \leqq i \leqq M).
  • 1 \leqq B_{i} \leqq N (1 \leqq i \leqq M).
  • A_{i} \ne B_{i} (1 \leqq i \leqq M).
  • (A_{i}, B_{i}) \ne (A_{j}, B_{j}) (1 \leqq i < j \leqq M).

小課題

小課題 1 [5 点]

  • N \leqq 100 を満たす.

小課題 2 [30 点]

  • N \leqq 5\,000 を満たす.

小課題 3 [65 点]

追加の制限はない.

入力例 1

5 4
1 2
1 3
4 3
4 5

出力例 1

10

たとえば次のような手順で 10 本の矢印を実現できる.

  1. 国 1 を仲介として,国 2 と国 3 が会議を行う.
  2. 国 4 を仲介として,国 3 と国 5 が会議を行う.
  3. 国 3 を仲介として,国 2 と国 5 が会議を行う.

出典

JOI 2013/2014 春季トレーニング合宿 Contest Day2 問題2