Tìm đồng đội

Có \(n\) học sinh, đánh số từ \(1\) đến \(n\). Hai học sinh \(u, v\) (\(u \ne v\)) có thể được ghép cặp để luyện tập với nhau nếu thỏa mãn một trong hai điều kiện sau:

• \(u\) và \(v\) đã từng luyện tập với nhau trước đó.

• Tồn tại một học sinh \(w\) sao cho \(u\) có thể ghép cặp với \(w\) và \(w\) có thể ghép cặp với \(v\).

Nói cách khác, mối quan hệ "có thể ghép cặp" là một quan hệ tương đương (chia \(n\) học sinh thành các nhóm liên thông).

Hãy ghép cặp các học sinh sao cho số lượng cặp học sinh luyện tập với nhau là nhiều nhất có thể (mỗi học sinh chỉ thuộc tối đa một cặp).

Input

• Dòng thứ nhất gồm hai số nguyên \(n, m\) (\(2 \le n \le 1000\), \(0 \le m \le \dfrac{n(n-1)}{2}\)).

• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) cho biết học sinh \(u_i, v_i\) đã từng luyện tập với nhau trước đó.

Output

In ra một số nguyên duy nhất là chênh lệch nhỏ nhất có thể giữa số học sinh của hai đội, hoặc \(-1\) nếu không tồn tại cách chia hợp lệ.

Example 1

Input:

5 7
1 2
1 3
3 4
5 4
2 5
4 1
2 3

Output:

1

Example 2

Input:

5 6
1 2
3 4
4 3
1 5
5 4
2 3

Output:

-1

Example 3

Input:

7 14
1 2
2 3
3 1
3 4
3 5
4 5
5 7
7 6
6 4
4 7
5 6
1 4
1 7
7 1

Output:

1

Note

Ở ví dụ thứ nhất, có thể chia đội \(\{1, 2, 3\}\) và đội \(\{4, 5\}\): mọi cặp học sinh trong đội \(\{1,2,3\}\) đều từng luyện tập với nhau (các cặp \(1\)-\(2\), \(1\)-\(3\), \(2\)-\(3\)), và đội \(\{4,5\}\) cũng vậy. Chênh lệch số học sinh là \(|3-2| = 1\), đây là chênh lệch nhỏ nhất có thể.

Ở ví dụ thứ hai, không tồn tại cách chia đội nào thoả mãn điều kiện nên đáp án là \(-1\).