Problem D
Inquiry II

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

Input

• The input starts with one line, containing integers $n$ ($1 \leq n \leq 100$), the number of vertices in the graph, and $m$ ($n-1 \leq m \leq n + 15$), the number of edges in the graph.

• Then follow $m$ lines, each containing integers $a, b$ ($1 \leq a, b \leq n$) indicating that there is an edge between vertices $a$ and $b$.

The graph given by this input is guaranteed to be both 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.

2 1
1 2

1

4 5
1 2
2 3
3 4
4 1
1 3

2