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.

-----Examples-----
Sample Input:
2 1
1 2
Sample Output:
1

Source: kattis | Difficulty: HARD


Solutions: