Quality Monitoring

Time limit1sMemory limit1024 MB

Summary

Find the largest set of joints where no two are adjacent, and output -1 unless that set has at least n-28 joints.

Level: Hard8 of 10
Topics: Graph, Backtracking, Greedy
Solved: No attempts yet

Problem

To provide better drinking water quality, the government is going to deploy some "smart devices" into the water supply system so that the quality of the water can be monitored. The water supply 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 no two devices may be adjacent. Enough devices must be 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.

Input

The first line of the input 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, the joints at the two ends of a pipe.

Output

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

Constraints

$2 \le n \le 3 \times 10^4$ , $1 \le m \le 5 \times 10^5$

Examples1

Example 1
Input
```
5 7
1 0
2 3
1 4
1 2
3 1
3 4
0 4
```
Expected output
```
2
```