17734번 - Making Friends is Fun 서브태스크다국어

あなたは歴史の裏舞台で活躍するエージェントであり，世界の平和に向けて日々活動を続けている．こ の世界には 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 ≤ i ≤ M) には 2 つの整数 A_i, B_i が空白を区切りとして書かれている．これは画用紙上に国 A_i を表す点から国 B_i を 表す点へ向かう矢印が描かれていること，すなわち国 A_i が国 B_i へ大使を派遣していることを表す．

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

• 1 ≤ N ≤ 100 000．
• 0 ≤ M ≤ 200 000．
• 1 ≤ A_i ≤ N (1 ≤ i ≤ M)．
• 1 ≤ B_i ≤ N (1 ≤ i ≤ M)．
• A_i ≠ B_i (1 ≤ i ≤ M)．
• (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ M)．