Có một số vấn đề xảy ra trong phòng tin học. Do đó, người ta đã kiểm tra lại hệ thống dây cáp của phòng học.

Biết rằng:

• Máy chủ luôn kết nối với máy số 1
• Mỗi sợi dây cáp chỉ kết nối giữa hai máy bất kỳ với nhau. Đồng nghĩa, thông tin có thể chuyển qua lại giữa 2 máy này
• Máy chủ có thể gửi thông tin đến các máy khác nếu máy chủ kết nối với máy đó hoặc kết nối trung gian qua 1 số máy khác.

** Quan trọng nhất : Đường dây liên thông khi và chỉ khi máy chủ có thể chuyển thông tin đến tất cả các máy còn lại (Bằng cách trực tiếp hoặc gián tiếp)**

Vì DeMen100ms là học sinh chuyên Tin, người ta đã nhờ anh thiết lập một chương trình trả lời câu hỏi :

• Nếu đường dây liên thông thì có thể cắt tối đa bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “-“ trước đáp án) (\(-0\) cũng là một đáp án có thể xảy ra)
• Ngược lại, thì phải gắn tối thiểu bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “+” trước đáp án)

Các bạn hãy giúp anh làm việc này nhé !

Input

• Dòng đầu là 2 số nguyên dương \(n\) và \(k\) lần lượt là số máy và số dây cáp của phòng học \((n, k \leq 10^6)\)
• \(k\) dòng tiếp theo, dòng thứ \(i\) là \(2\) số nguyên dương \(a_i, b_i\) : Dây cáp thứ \(i\) nối 2 máy \(a_i\) và \(b_i\). \((a_i, b_i \leq n, a_i \neq b_i)\)

Output

• In ra kết quả của câu hỏi trên

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 5, k \leq 10\)
• Subtask \(2\) (\(30\%\) số điểm): \(n, k \leq 10^3\)
• Subtask \(1\) (\(40\%\) số điểm): \(n, k \leq 10^6\)

Example

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

-1

4 3
1 2
2 3
3 1

1