B. KINGDOM

Đất nước Bụng Bự đang bị giặc ngoại xâm hoành hành và chiến lược gia đại tài FatEqual đang lên kế hoạch để đối phó với quân thù. Đất nước Bụng Bự có thị trấn được đánh số từ đến và được kết nối liên thông với nhau bằng con đường. FatEqual sẽ lên kế hoạch phòng thủ tối đa thị trấn sao cho thị trấn bất kì được phòng thủ có thể đến được với nhau mà chỉ đi qua các thị trấn đang được phòng thủ. Độ tốt của kế hoạch đó là độ dài một đoạn liên tiếp sao cho các thị trấn có chỉ số từ đến đều được phòng thủ. FatEqual muốn tính xem độ tốt lớn nhất của kế hoạch mà mình có thể lên là bao nhiêu. Các bạn hãy giúp FatEqual nhé!

Dữ liệu vào:

• Dòng đầu tiên bao gồm số và ;
• dòng tiếp theo mỗi dòng gồm hai số nguyên dương miêu tả một con đường trong thị trấn.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là độ dài lớn nhất của đoạn liên tiếp mà FatEqual có thể phòng thủ.

Ví dụ

Dữ liệu vào:

12 10
11 2
2 1
11 7
7 4
11 10
1 6
11 8
4 0
1 5
11 3
7 9

Dữ liệu ra:

9

Giải thích:

• Chọn tập đỉnh . Khi đó đoạn liên tiếp lớn nhất ta có thể tìm là .

Giới hạn:

• Subtask số điểm có ;
• Subtask số điểm khác có và bậc của mỗi đỉnh tối đa bằng ;
• Subtask số điểm còn lại có .