시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 11 7 7 63.636%

문제

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