Farmer John은 $N$개 목초지($1 \leq N \leq 50,000$)를 가지고 번호는 $1...N$이며 $M$개 양방향 길($1 \leq M \leq 100,000$)로 연결됩니다. 길 $i$는 $A_i$($1 \leq A_i \leq N$)와 $B_i$($1 \leq B_i \leq N$)를 연결하고 $A_i != B_i$입니다. 같은 목초지 쌍을 두 길이 연결할 수 있습니다.

Bessie는 FJ 생일을 위해 꾸밉니다. 각 목초지에 '$F$' 또는 '$J$'의 큰 표지판을 두고, 혼란을 막기 위해 길로 연결된 두 목초지는 다른 글자를 써야 합니다.

회사에서 '$F$'가 '$J$'보다 비싸므로 '$J$' 수를 최대화합니다. 그 수를 구하고 올바른 배치가 없으면 -1을 출력하세요.

입력

• 1번째 줄: 정수 $N$, $M$.
• $2..M+1$번째 줄: 정수 $A_i$, $B_i$로, $A_i$와 $B_i$ 사이 양방향 길을 나타냅니다.

출력

• 1번째 줄: '$J$' 표지판 수의 최댓값인 정수. 올바른 해가 없으면 -1을 출력합니다.

예제

입력 1

4 4
1 2
2 3
3 4
4 1

출력 1

2

참고

목초지와 길이 정사각형의 꼭짓점과 변을 이룹니다.

Bessie는 목초지 1과 3을 '$J$'로 하거나 대신 2와 4를 선택할 수 있습니다.

문제 작성자: Kalki Seksaria, 2014