Informatica Online Judge

  36석표야 운동해! [2367 / 093F]

Time Limit(Test case) : 500 (ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : gs18050 - ms / 2681byte
My Best Submission (C++) : N/A

[36th 박준호(gs18050)]
Writer ID : [gs18050]

Background

석표는 경곽에서도 유명한 핫식스 중독자 약골이다.

매일 핫식스를 3캔씩 마신다는 소문이 있는 석표는 이번 셔틀런에서 무려 18개라는 신기록을 세웠다.

이에 감탄한 체력왕 민준은 석표와 함께 운동하기로 결정하였다. 마침 학교 뒤에 체육 동아리에서도 기슭까지밖에 가지 못했었다는 소문의 광교산이 있기 때문에 광교산을 등산하려고 한다.

광교산은 정점 N개, 간선 M개로 이루어진 그래프 구조이다. 한 번 운동할 때 힘든 정도는 운동하며 지나간 길들의 길이 Li들의 합으로 정의된다.

짝수에 대한 강박증이 있는 민준은 석표에게 홀수만큼 힘든 운동을 할 수 있는 경로에 포함된 모든 정점을 이용하지 않고 짝수만큼 힘든 운동을 시키려고 한다.

이 때 석표는 가능한 출발점들 사이의 간선들 중 일부에 핫식스를 숨겨놓으려고 한다.

핫식스를 숨길 수 있기 위해서는 해당 길이 연결하고 있는 두 정점과 연결된 간선들 중에 핫식스를 숨겨놓았으면 안된다.

간단히 이야기하면 가능한 출발점들 사이의 최대 매칭의 개수를 구하라는 것이다.

석표는 운동을 시작하기 전에 빨리 핫식스를 사서 숨겨놓아야 하므로 당신에게 구매해야 하는 핫식스의 개수를 구하는 프로그램을 부탁하였다. 석표를 위해 프로그램을 구현하여주자.

Input

첫 번째 줄에 정점의 개수 N과 정점들을 이어주는 길의 개수 M이 공백으로 구분되어 입력된다.
두 번째 줄에 각 M개의 길이 연결하는 두 정점의 번호가 입력된다.
0<=N<=7000
0<=M<=10000

Output

석표가 구매해야 하는 핫식스의 개수를 출력하시오.

IO Example

입력 예제
6 7
1 2
2 3
3 1
1 4
4 5
5 6
6 1

출력 예제
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]