Vào một hôm, cậu học sinh Z sang nhà bạn mình chơi game. Trò chơi hai bạn chơi được mô tả như sau:

Một khu di tích lịch sử lâu đời gồm có N khu vực và M đường đi hai chiều. Trò chơi được thiết kế đảm bảo rằng luôn luôn có đường đi lại giữa hai khu vực bất kỳ. Một nhà thám hiểm sẽ bắt đầu từ vị khu vực s và đi đến khu vực t (s và t không biết trước và có thể được chọn bất kì cặp đỉnh nào trong đồ thị).

Cảm thấy trò chơi quá nhàm chán vì quá dễ nên Z quyết định thêm một số lương con quái vật được đặc trên các con đường đi để tăng độ hấp dẫn của trò chơi. Z muốn đặc các con quái vật sao cho thỏa các yêu cầu sau:

- Mỗi đường đi chỉ có nhiều nhất 1 con quái vật.

- Các con quái vật sẽ được đặt ở các con đường mà khi đi từ vị trí s đến t không thể không đi qua con đường này.

Hãy giúp Z đếm số lượng quái vật lớn nhất có thể đặc trên một đường đi từ s đến t.

Dữ liệu vào:

Dòng đầu tiên gồm hai số N và M (2 <= n <= 2 * 10^5, n – 1 <= m <= 4 * 10^5) - số lượng khu vực và số đường đi.

M dòng tiếp theo mỗi dòng gồm hai số u và v là hai khu vực có đường đi trực tiếp đến nhau.

Dữ liệu ra:

Một số duy nhất là số lượng quái vật có thể đặt.