Problem : 365 - 2B. 來加邊吧！

Problem Statistics

Solved Member: 13　　Submission: 58　　User Tried: 13

Statement:

有 N 點 M 邊的有向圖，點從 1 編號 N。我們用 (i,j) 來表示由 i 連到 j 的有向邊。

你每次可以做一種操作：
step 1：挑 1 個點 x，並選擇 x 連出的兩個點 y,z
step 2：加上邊 (y,z) 跟 (z,y) (如果邊原本就存在的話則不加)

你可以依照任意順序加上你想要的邊，直到不能加任何邊為止。
問你最多可以讓整張圖有幾條有向邊？

Input:Output:

第一行有兩個整數 N,M，代表點數和有向邊的數量。
接下來 M 行，每行兩個整數 Ai,Bi，代表有一條從 Ai 連到 Bi 的有向邊。

限制：
1 ≤ N ≤ 100000
1 ≤ M ≤ 200000
1 ≤ Ai,Bi ≤ N
輸入沒重邊，沒自環

Subtask 1：(5分)
N ≤ 100

Subtask 2：(30分)
N ≤ 5000

輸出一個數字，代表加邊之後，最多能有幾條有向邊。

Sample Input:Sample Output:

5 4
1 2
1 3
4 3
4 5

HINT:

範例測資解釋：
1. x=1, y=2, z=3，加上 (2,3) (3,2) 兩條邊
2. x=4, y=3, z=5，加上 (3,5) (5,3) 兩條邊
3. x=3, y=2, z=5，加上 (2,5) (5,2) 兩條邊

變成 4+6=10 條邊

Source:

2013/2014 JOI 合宿 2模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	262144kb
1-1	500ms	262144kb	5
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
1-6	500ms	262144kb
1-7	500ms	262144kb
1-8	500ms	262144kb
1-9	500ms	262144kb
1-10	500ms	262144kb
1-11	500ms	262144kb
1-12	500ms	262144kb
1-13	500ms	262144kb
1-14	500ms	262144kb
1-15	500ms	262144kb
1-16	500ms	262144kb
1-17	500ms	262144kb
1-18	500ms	262144kb
2-1	500ms	262144kb	30
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
2-6	500ms	262144kb
2-7	500ms	262144kb
2-8	500ms	262144kb
2-9	500ms	262144kb
2-10	500ms	262144kb
2-11	500ms	262144kb
2-12	500ms	262144kb
2-13	500ms	262144kb
2-14	500ms	262144kb
2-15	500ms	262144kb
2-16	500ms	262144kb
2-17	500ms	262144kb
2-18	500ms	262144kb
2-19	500ms	262144kb
2-20	500ms	262144kb
2-21	500ms	262144kb
2-22	500ms	262144kb
2-23	500ms	262144kb
2-24	500ms	262144kb
2-25	500ms	262144kb
2-26	500ms	262144kb
2-27	500ms	262144kb
2-28	500ms	262144kb
3-1	500ms	262144kb	65
3-2	500ms	262144kb
3-3	500ms	262144kb
3-4	500ms	262144kb
3-5	500ms	262144kb
3-6	500ms	262144kb
3-7	500ms	262144kb
3-8	500ms	262144kb
3-9	500ms	262144kb
3-10	500ms	262144kb
3-11	500ms	262144kb
3-12	500ms	262144kb
3-13	500ms	262144kb
3-14	500ms	262144kb
3-15	500ms	262144kb
3-16	500ms	262144kb
3-17	500ms	262144kb
3-18	500ms	262144kb
3-19	500ms	262144kb
3-20	500ms	262144kb
3-21	500ms	262144kb
3-22	500ms	262144kb
3-23	500ms	262144kb
3-24	500ms	262144kb
3-25	500ms	262144kb
3-26	500ms	262144kb
3-27	500ms	262144kb
3-28	500ms	262144kb
3-29	500ms	262144kb
3-30	500ms	262144kb
3-31	500ms	262144kb
3-32	500ms	262144kb
3-33	500ms	262144kb
3-34	500ms	262144kb
3-35	500ms	262144kb
3-36	500ms	262144kb
3-37	500ms	262144kb