Trong lớp học của thầy Trí có \(n\) học sinh và \(m\) mối quan hệ bạn bè giữa họ. Nhiệm vụ của bạn là chia các học sinh thành hai đội sao cho không có hai người bạn nào trong cùng một đội. Bạn có thể tự do chọn quy mô của mỗi đội.

Input

• Dòng đầu tiên của dữ liệu đầu vào có hai số nguyên \(n\) và \(m\), lần lượt là số học sinh và số mối quan hệ bạn bè giữa họ. Các học sinh được đánh số từ \(1\) đến \(n\).
• Dòng tiếp theo chứa \(m\) dòng mô tả các mối quan hệ bạn bè. Mỗi dòng có hai số nguyên \(a\) và \(b\), cho biết học sinh \(a\) và học sinh \(b\) là bạn bè.

Output

• Nếu chia được thì in \(1\). Không chia được thì in \(-1\)

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le a,b \le n\)

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

1