시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

To provide a better drinking quality, the government is going to deploy some “smart devices” into the water supplying system so that the quality of the water can be monitored. The water supplying system consists of many pipes, and two pipes are connected by a joint. You may assume that the system forms a connected simple graph, with pipes being the edges and joints being the vertices. An example is given in the following figure.

The smart devices are designed to be deployed at the joints. However, two adjacent devices may interfere with each other, so it is required that no two devices are adjacent. There have to be enough number of devices deployed so that the system can be fully monitored. Formally, the system is fully monitored if

  • there are at least n − 28 devices deployed, and
  • no two devices are adjacent.

Please determine whether the system can be fully monitored. If the answer is no, output −1; otherwise, output the maximum number of devices that can be deployed.

입력

The first line of the input file contains two positive integers n and m, where n is the number of joints, numbered from 0 to n − 1, and m is the number of pipes. Each of the following m lines contains two nonnegative integers, indicating the joints at two ends of a pipe.

출력

Output an integer: “-1” if the system cannot be fully monitored; otherwise, the maximum number of devices that can be deployed.

제한

  • 2 ≤ n ≤ 3 × 104, 1 ≤ m ≤ 5 × 105

예제 입력 1

5 7
1 0
2 3
1 4
1 2
3 1
3 4
0 4

예제 출력 1

2