VMRELATE - Làm mai mối
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Các đảo dừa muốn kết làm thông gia với nhau để tăng thêm tình đoàn kết. Trong vụ việc này, cư dân trên các đảo tín nhiệm mời Pirate, chàng trai bị thất tình nhiều nhất trong quần đảo, đứng ra làm mai mối. Pirate vốn đang đau đớn đọc đống thư chia tay trong email của mình nhưng đành phải gạt nước mắt sang một bên lên để đường làm nhiệm vụ. Tất cả vì sự hòa bình của quần đảo!
Pirate biết rằng mấu chốt trong sự thành công của một cuộc hôn nhân phụ thuộc vào sự quen biết từ trước của hai bên. Tức là nếu hai vương quốc càng có mối quan hệ càng khăng khít thì khả năng họ chấp nhận tổ chức hôn sự càng cao.
Nhưng làm sao xác định được mối quan hệ của các quốc đảo? Sau khi nghiên cứu, Pirate nhận ra rằng các đảo được nối với nhau bởi một số cây cầu dừa. Độ dài của đường đi từ đảo này đến đảo kia tỉ lệ với số cây cầu dừa phải đi qua trên con đường đó.
Dựa vào nghiên cứu trên, Pirate sáng chế ra một thước đo độ khăng khít giữa các hòn đảo, gọi là phương pháp "khoảng cách trung gian" . Phương pháp này được áp dụng để ước lượng độ khăng khít của hai hòn đảo có cầu dừa nối với nhau. Giả sử ta áp dụng vào hai đảo x và y (có cầu dừa nối x và y) . Ta sẽ chọn ra một đỉnh z trung gian (có đường đi đến x hoặc y) , rồi tính chênh lệch (giá trị tuyệt đối của hiệu) giữa đường đi ngắn nhất từ z đến x và từ z đến y. Khoảng cách trung gian giữa x và y chính là chênh lệch nhỏ nhất trong tất cả các cách chọn đỉnh z trung gian trong quần đảo.
Pirate sẽ thử nghiệm tác hợp cho hai hòn đảo có khoảng cách trung gian nhỏ nhất. Hãy giúp anh ấy tìm ra giá trị trên!
Input
Input gồm nhiều dòng:
- Dòng thứ nhất là số nguyên T , số bộ test.
-
Với mỗi bộ test, được ngăn cách với nhau bởi một dòng trống, gồm:
- Dòng đầu tiên gồm hai số nguyên N và M , số hòn đảo và số cây cầu dừa nối các đảo.
- M dòng tiếp theo, mỗi dòng chứa hai số nguyên u v , thể hiện một cây cầu dừa nối hai đảo u và v. Các cây cầu dừa có thể được đi lại theo cả hai hướng. Không có cây cầu dừa nào nối một đảo với chính nó.
Output
Output gồm T dòng:
- Mỗi dòng ghi ra một số nguyên thể hiện khoảng cách trung gian nhỏ nhất giữa hai hòn đảo của test tương ứng.
Example
Input: 2
4 4
1 2
2 3
3 4
4 1
4 5
1 2
2 3
3 4
4 1
4 2
Output: 1
0
Giải thích: Ở test thứ nhất, khoảng cách trung gian nhỏ nhất là giữa hai thành phố 1 và 2. Ở test thứ hai, khoảng cách trung gian nhỏ nhất là giữa hai thành phố 2 và 4.
Giới hạn
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 10 5
- 1 ≤ M ≤ 10 5
- Trong 40% số test, 1 ≤ N ≤ 100
- Người up: voj