RabbitWalking

시간 제한8초메모리 제한512 MB

요약

단순 무방향 그래프가 주어질 때, 홀수 길이의 닫힌 보행이 없도록 간선을 최대로 추가한 수를 구하고, 이미 그러한 상태라면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 그래프, 유니온 파인드, BFS, 그리디
정답자: 아직 제출이 없습니다

문제

토끼가 사는 도시에는 $V$ 개의 교차로와 $E$ 개의 도로가 있다. 교차로에는 1부터 시작하는 번호가 붙어 있다. $i$ 번째 도로는 교차로 $a_i$ 와 교차로 $b_i$ 를 양방향으로 연결한다.

토끼는 산책과 홀수를 좋아한다. 토끼는 어떤 교차로에서 출발해 도로를 홀수 번 따라가 출발한 정점으로 돌아오는 경로를 따라 산책하고 싶어 한다.

이 도시의 시장인 고양이는 도시 내 이동을 효율적으로 만들기 위해 서로 다른 두 교차로를 잇는 도로를 많이 추가하려고 한다. 다만 어떤 교차로 쌍에 대해서도 놓을 수 있는 도로는 최대 1개이다. 또 고양이는 장난을 좋아해서, 도로를 홀수 번 따라가 출발한 정점으로 돌아오는 경로가 포함되지 않게 하려고 한다.

도로를 최대 몇 개까지 추가할 수 있는지 구하라. 처음부터 토끼의 요구가 만족되어 있으면 -1을 출력하라.

입력

입력은 다음 형식으로 주어진다:

$V$ $E$

$a_1$ $b_1$

...

$a_E$ $b_E$

출력

추가할 수 있는 도로 개수의 최댓값을 나타내는 정수를 한 줄에 출력하라. 처음부터 토끼의 요구가 만족되어 있으면 -1을 출력하라.

제한

$V$ 는 1 이상 100,000 이하이다.
$E$ 는 0 이상 100,000 이하이다.
$a_i$ 와 $b_i$ 는 서로 다르다.
같은 교차로 쌍을 잇는 도로는 두 개 이상 존재하지 않는다.

예제2

예제 1
입력
```
8 5
1 2
6 5
6 4
1 3
4 7
```
예상 출력
```
11
```
예제 2
입력
```
5 8
2 1
2 4
1 3
5 4
4 1
2 3
3 5
2 5
```
예상 출력
```
-1
```