품질 감시

음용수의 품질을 높이기 위해 정부는 수도 공급 시스템에 "스마트 장치"를 설치해 물의 품질을 감시하려고 한다. 수도 공급 시스템은 여러 개의 관으로 이루어지며, 두 관은 이음매로 연결된다. 시스템은 연결된 단순 그래프를 이룬다고 가정할 수 있으며, 이때 관은 간선, 이음매는 정점에 해당한다. 예는 다음 그림과 같다.

스마트 장치는 이음매에 설치한다. 다만 인접한 두 장치는 서로 간섭하므로, 어떤 두 장치도 인접해서는 안 된다. 시스템을 완전히 감시하려면 장치가 충분히 설치되어야 한다. 형식적으로, 다음 두 조건을 모두 만족하면 시스템이 완전히 감시된다.

• 설치된 장치가 적어도 $n - 28$개 이상이다.
• 어떤 두 장치도 인접하지 않는다.

입력의 첫 줄에는 두 양의 정수 $n$과 $m$이 주어진다. $n$은 0부터 $n - 1$까지 번호가 매겨진 이음매의 개수이고, $m$은 관의 개수이다. 이후 $m$개의 줄에는 각각 관의 양 끝에 있는 이음매 번호를 나타내는 0 이상의 정수 두 개가 주어진다.

정수 하나를 출력한다. 시스템을 완전히 감시할 수 없으면 "$-1$"을 출력한다. 그렇지 않으면 설치할 수 있는 장치 수의 최댓값을 출력한다.

$2 \le n \le 3 \times 10^4$, $1 \le m \le 5 \times 10^5$