View problem - 작은 사이클들 (YDX13_smallcycles)

Language	Compilation command
C11	/usr/bin/gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o E E.c -lm
C++20	/usr/bin/g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o E E.cpp
C++17	/usr/bin/g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o E E.cpp
Java	/usr/bin/javac -encoding UTF-8 E.java /bin/sh -c echo "Main-Class: E" > __manifest__.txt /bin/sh -c jar cfm E.jar __manifest__.txt *.class
Pypy 3	/usr/bin/pypy3 -m compileall -b E.py /bin/mv E.pyc __main__.pyc /usr/bin/zip E.pyz.zip __main__.pyc /bin/mv E.pyz.zip E.pyz

Time limit	Memory limit	# of submissions	# of submitted users	Solved #	Accepted user ratio
2000 ms	256 MiB	7	4	3	75.00%

승현이는 무방향 그래프 $G$ 를 가지고 있습니다. 이 그래프는 아래 조건들을 만족합니다.

$G$ 는 단순(simple) 그래프입니다. 즉, 루프 (자기 자신을 잇는 간선) 또는 중복 간선 (두 정점 사이에 간선이 2개 이상 있는 경우)가 존재하지 않습니다.
$G$ 는 연결(connected) 그래프입니다.
$G$ 는 길이가 적어도 4인 단순 사이클을 포함하지 않습니다. $k$ 개의 서로 다른 정점들의 튜플 $v_{1}, v_{2}, \cdots, v_{k}$ 이 "길이가 $k$ 인 단순 사이클"이 될 조건은 각 $i$ 에 대해 $v_{i}$ 와 $v_{i+1}$ 사이에 간선으로 연결되어 있어야 하고, $v_{1}$ 과 $v_{k}$ 역시 간선으로 연결되어 있어야 합니다.

승현이가 위 조건을 만족하면서 $G$ 에 추가할 수 있는 가장 많은 간선의 수를 구하는 프로그램을 작성하세요. 승현이는 어떤 두 정점의 쌍 사이에도 간선을 추가할 수 있습니다.

입력 형식

첫 번째 줄에는 두 개의 정수 $V$ ( $1 \le V \le 10^{5}$ )와 $E$ ( $0 \le E \le 10^{5}$ )가 공백을 사이로 두고 주어집니다. $V$ 는 $G$ 의 정점의 수이고, $E$ 는 $G$ 의 간선의 수입니다.

다음 $E$ 개 줄에는 간선들의 정보가 주어집니다. 이 중 $i$ 번째 줄에는 두 개의 정수 $a_{i}$ 와 $b_{i}$ 가 공백을 사이로 두고 주어집니다. ( $1 \le a_{i} < b_{i} \le V$ ) $a_{i}$ 와 $b_{i}$ 는 $i$ 번 간선이 잇는 두 정점의 번호입니다. 정점들은 $1$ 부터 $V$ 까지 번호가 붙어 있습니다. 입력에서 주어지는 그래프는 위의 조건을 만족함은 보장됩니다.

출력 형식

승현이가 추가할 수 있는 가장 많은 간선의 수를 출력합니다.

예제

예제 1

입력

출력

예제 2

입력