정치인

총선이 또 한 번 끝났다. 갓 취임한 리지오 총리의 첫 과제는 내각 구성이다. 리지오는 자기 당 소속 의원 $n$명 가운데에서 장관을 뽑기로 했다. 의원에게는 $0$번부터 $n-1$번까지 번호가 붙어 있다.

문제는 후보마다 같은 당 동료 중 함께 일하기 싫은 사람의 명단을 총리에게 냈다는 점이다. 이 관계는 양쪽에 똑같이 적용된다. A가 B와 일하기 싫어하면 B도 A와 일하기 싫어한다. 게다가 의원마다 자신이 뽑히지 않으면 야당으로 넘어가겠다고 으름장을 놓았다. 그래서 $n$명 전원에게 자리를 줘야 한다.

리지오 총리는 오래 고민하지 않고 다음 타협안을 내놓았다.

1. 후보 중 일부는 내각에 들어가고, 나머지는 아주 중요한 회사의 이사회로 간다.
2. 내각에도 이사회에도 서로 함께 일하기 싫어하는 세 사람이 함께 앉지 못한다. 즉 A와 B, A와 C, B와 C가 모두 함께 일하기 싫어하는 사이인 세 사람 A, B, C가 같은 기관에 모두 배정되는 일은 없다.

사이가 나쁜 두 사람이 같은 기관에 앉는 것은 규칙 2에 걸리지 않는다. 금지되는 경우는 세 사람이 서로서로 싫어할 때뿐이다. 두 기관 중 한쪽이 비어도 된다.

야당 대표는 이 정도는 문제도 아니라고 공언했다. 후보를 전원 뽑아야 하는 것이 아니라면, 내각과 이사회, 뽑히지 않은 의원 모임 어디에도 서로 일하기 싫어하는 두 사람이 함께 있지 않도록 나눌 수 있다는 것이다. 야당 대표의 말은 사실이라고 가정해도 된다.

리지오 총리는 규칙 2를 지키면서 내각을 최대한 크게 만들고 싶다. 장관 수의 최댓값을 구하여라.

첫 줄에 당 소속 의원 수 $n$과 함께 일하기 싫어하는 후보 쌍의 수 $m$이 공백 하나를 사이에 두고 주어진다. ($1 \le n \le 18$, $0 \le m \le n(n-1)/2$)

다음 $m$개 줄에는 각각 두 정수 $a$, $b$ ($0 \le a < b < n$)가 주어진다. $a$번 의원과 $b$번 의원이 서로 함께 일하기 싫어한다는 뜻이다. 같은 쌍은 두 번 주어지지 않는다.

내각에 앉을 수 있는 의원 수의 최댓값을 한 줄에 출력한다. 내각에도 이사회에도 서로서로 함께 일하기 싫어하는 세 사람이 들어가면 안 되며, 내각에 뽑히지 않은 의원은 모두 이사회로 간다.