Inquiry II

Time limit5sMemory limit512 MB

Summary

Given a connected simple graph with at most n+15 edges, output the size of its maximum independent set.

Level: Hard8 of 10
Topics: Tree, DFS, Dynamic programming, Greedy
Solved: No attempts yet

Problem

For an undirected, simple graph $G = (V, E)$ , a subset $V' \subseteq V$ is an independent set if no two elements of $V'$ are connected by an edge. An independent set of $G$ is a maximum independent set if no independent set in $G$ has strictly more vertices. Given a specific kind of connected graph $G$ , find the size of a maximum independent set of $G$ .

Input

The first line contains integers $n$ ( $1 \le n \le 100$ ), the number of vertices in the graph, and $m$ ( $n - 1 \le m \le n + 15$ ), the number of edges in the graph.
Then $m$ lines follow, each containing integers $a, b$ ( $1 \le a, b \le n$ ) indicating that there is an edge between vertices $a$ and $b$ .

The graph given by this input is simple and connected: there is at most one edge between each pair of vertices, there are no loops, and there is a path between each pair of vertices.

Output

Output the number of vertices in a maximum independent set of the input graph.

Examples2

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