시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB119504449.438%

## 문제

For an undirected, simple graph G = (V, E) we call a subset V' ⊆ 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.

## 입력

• The input starts with one line, containing integers n (1 ≤ n ≤ 100), the number of vertices in the graph, and m (n − 1 ≤ m ≤ n + 15), the number of edges in the graph.
• Then follow m lines, each containing integers a, b (1 ≤ a, b ≤ 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 the number of vertices in a maximum independent set of the input graph.

## 예제 입력 1

2 1
1 2


## 예제 출력 1

1


## 예제 입력 2

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


## 예제 출력 2

2


## 출처

• 문제를 만든 사람: Timon Knigge