Inquiry II

시간 제한5초메모리 제한512 MB

요약

간선이 최대 n+15개인 연결 단순 그래프가 주어질 때, 최대 독립 집합의 크기를 출력한다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

무향 단순 그래프 $G = (V, E)$ 에서 $V' \subseteq V$ 의 어떤 두 원소도 간선으로 연결되지 않으면 $V'$ 를 독립 집합이라고 한다. $G$ 의 독립 집합 중에서 원소 수가 더 많은 독립 집합이 존재하지 않으면 그 집합을 최대 독립 집합이라고 한다. 특정한 종류의 연결 그래프 $G$ 가 주어질 때, $G$ 의 최대 독립 집합의 크기를 구하라.

입력

첫 줄에 정수 $n$ ( $1 \le n \le 100$ )과 $m$ ( $n - 1 \le m \le n + 15$ )이 주어진다. $n$ 은 그래프의 정점 수, $m$ 은 간선 수이다.
이어서 $m$ 개의 줄이 주어지고, 각 줄에는 정수 $a, b$ ( $1 \le a, b \le n$ )가 주어져 정점 $a$ 와 $b$ 사이에 간선이 있음을 나타낸다.

입력으로 주어지는 그래프는 단순하고 연결되어 있다. 즉, 각 정점 쌍 사이에는 간선이 최대 하나이고, 자기 자신으로 향하는 간선이 없으며, 모든 정점 쌍 사이에 경로가 존재한다.

출력

입력 그래프의 최대 독립 집합에 속하는 정점의 수를 출력한다.

예제2

예제 1
입력
```
2 1
1 2
```
예상 출력
```
1
```
예제 2
입력
```
4 5
1 2
2 3
3 4
4 1
1 3
```
예상 출력
```
2
```