겨울 축제

피터가 가장 좋아하는 계절은 겨울이다. 축제에 빠진 피터는 도시를 장식하고 싶어 한다.

도시에는 아이스 스케이팅, 스키, 눈싸움 같은 활동을 할 수 있는 지역이 많다. 일부 지역 쌍을 잇는 도로가 있다. 피터는 각 도로를 따라 특별한 장식을 달고 싶어 한다. 장식은 비용이 0, 1, 2인 세 종류가 있다.

피터는 장식이 다음 조건을 만족하기를 원한다.

• 한 지역에 인접한 서로 다른 도로 두 개를 고른다. 두 도로에 달린 장식의 비용을 각각 $a$, $b$라 하면 $(a + b) \bmod 3 \neq 1$이어야 한다.
• 임의의 사이클을 따라 있는 장식 비용의 합은 홀수여야 한다.

사이클은 도로로 연결된 지역들이 고리를 이루는 순서열이다. 각 지역은 고리에 한 번만 나타날 수 있다.

피터는 원하는 방식으로 도시를 장식하는 데 드는 최소 비용을 알고 싶어 한다.

각 입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력에 대해 여러 번 실행될 수 있다.

각 테스트 케이스는 두 정수 $n$과 $m$($1 \le n, m \le 10^5$)이 적힌 줄로 시작한다. 여기서 $n$은 지역의 수, $m$은 도로의 수이다. 지역은 1부터 $n$까지 번호가 매겨져 있다.

이어지는 $m$개의 줄에는 각각 두 정수 $a$, $b$($1 \le a < b \le n$)가 주어지며, 이는 지역 $a$와 $b$를 직접 잇는 도로가 있다는 뜻이다. 같은 두 지역을 잇는 도로는 없다. 도로를 따라 모든 지역에서 다른 모든 지역으로 갈 수 있을 수도 있고 없을 수도 있다.

조건을 지키며 도시를 장식하는 최소 비용을 한 개의 정수로 출력한다. 피터의 조건에 맞게 도시를 장식하는 것이 불가능하면 $-1$을 출력한다.