DISTANCE - Khoảng cách 2
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

An và Bình là đôi bạn thân từ nhỏ, bây giờ họ đều đã lớn và lập gia đình. Song, vì vẫn muốn giữ tình bạn đẹp, họ quyết định xây nhà gần nhau và trở thành hàng xóm của nhau. Tuy nhiên An và Bình là hai người kỳ lạ, họ rất thích các số nguyên tố, đặc biệt là số 2 vì đó là số nguyên tố duy nhất là số chẵn, vì vậy, thay vì xây nhà sát nhau, họ quyết định xây nhà sao cho khoảng cách ngắn nhất giữa hai ngôi nhà là 2.

Khu An và Bình ở có n mảnh đất trống được đánh số từ 1 tới n và m con đường hai chiều nối trực tiếp giữa hai mảnh đất. Đặc biệt, giữa hai mảnh bất kì đất luôn tồn tại đường đi giữa chúng. Vì An và Bình quyết định mua đất ở khu này để xây nhà, nhiệm vụ của bạn là tính xem An và Bình có thể chọn 2 mảnh đất nào để xây nhà thỏa mãn sở thích của hai người.

Dữ liệu vào

Dòng thứ nhất ghi 2 số n và m

m dòng tiếp theo, mỗi dòng ghi 2 số u và v với ý nghĩa có con đường hai chiều nối trực tiếp 2 mảnh đất u và v

Dữ liệu ra

Gồm 1 dòng duy nhất là số cặp mảnh đất mà An và Bình có thể chọn để xây nhà thỏa mãn sở thích của hai người

Giới hạn

1 <= m < n <= 105

Ví dụ

  • input
    3 2
    1 2
    2 3
    output
    1

An và Bình có thể chọn mảnh đất 1 và 3 để xây nhà vì khoảng cách ngắn nhất giữa chúng là 2 nếu ta đi theo cách sau: 1 - 2 - 3
 

Back to Top