Khi Leonhard Euler giải được bài toán cầu Königsberg nổi tiếng, ông không hề biết mình đã khám phá ra một lĩnh vực toán học hoàn toàn mới - lý thuyết đồ thị!

Thật không may, bài toán cầu Königsberg lại quá dễ dàng đối với lập trình viên của thời đại này, nên Euler đã nghĩ ra một bài toán khác - bài toán cầu Zagreb!

Các cây cầu của Zagreb tạo thành một đồ thị có ~n~ đỉnh và ~m~ cạnh trong đó các cạnh biểu thị các cây cầu và các đỉnh biểu thị các đảo ven sông. Đồ thị liên thông, nói cách khác, có thể đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác bằng cách di chuyển qua các cạnh. Bây giờ Euler hỏi, có bao nhiêu cạnh sao cho sau khi loại bỏ chúng, đồ thị trở nên không liên thông?

Một lần nữa, Euler không biết rằng bài toán này ngày nay cũng nổi tiếng (những blog Codeforces chết tiệt đó). Vì vậy, tác giả của bài toán này quyết định đưa ra cho bạn một câu hỏi thậm chí còn khó hơn, có bao nhiêu cạnh sao cho sau khi loại bỏ các đỉnh mà nó kết nối, ~n − 2~ nút còn lại sẽ không liên thông?

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~4 \leq n \leq 10^5, n-1 \leq m \leq 3 \times 10^5~) mô tả số đỉnh và số cạnh của đồ thị.
• Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên dương ~a_i~ và ~b_i~ (~1 \leq a_i, b_i \leq n~) mô tả cạnh thứ ~i~ nối hai đỉnh ~a_i~ và ~b_i~. Đảm bảo không có cạnh khuyên và cạnh lặp.

Output

Đưa ra một dòng duy nhất là kết quả của bài toán.

Scoring

1. ~n \leq 100, m \leq 300~ (13 điểm)

2. ~n \leq 1000, m \leq 3000~ (17 điểm)

3. ~n \leq 1000~ (25 điểm)

4. ~m - n \leq 20~ (12 điểm)

5. Không có ràng buộc gì thêm (43 điểm)

Sample Input 1

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

Sample Output 1

1

Sample Input 2

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

Sample Output 2

4

Explanation

Ở ví dụ đầu tiên, ta chỉ có thể xóa cạnh ~(1,3)~ cùng với hai đỉnh ~1~ và ~3~.

Ở ví dụ thứ hai, ta có thể xóa các cạnh sau: ~(1,2)~, ~(2,4)~, ~(2,6)~, ~(2,5)~.