Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Mạng chẵn lẻ
Một mạng gồm N máy tính đánh số từ 1 đến N, và M kênh truyền tin một chiều giữa một số cặp máy tính trong mạng được đánh số từ 1 đến M. Mạng máy tính là thông suốt, nghĩa là từ một máy có thể truyền tin đến một máy bất kỳ khác trong mạng bằng đường nối trực tiếp hoặc thông qua các máy trung gian. Một máy trong mạng có bậc chẵn nếu số kênh truyền trực tiếp từ nó đến các máy khác là chẵn. Một máy trong mạng có bậc lẻ nếu số kênh truyền trực tiếp từ nó đến các máy khác là lẻ.
Giả sử s và t là hai máy bậc lẻ trong mạng, hãy đổi hướng truyền tin của một số kênh để biến đổi mạng đã cho thành mạng (không nhất thiết phải thông suốt) mà trong nó hai máy s và t trở thành hai máy bậc chẵn và không làm thay đổi tính chẵn lẻ của các máy khác trong mạng. Số kênh đổi hướng càng ít càng tốt.
Dữ liệu vào từ file NET.INP:
-          Dòng đầu chứa hai số N và M (N <= 2000, M <= 10000).
-          Dòng thứ hai chứa hai số s và t.
-          Dòng thứ i trong M dòng tiếp theo chứa hai số ui và vi cho biết có kênh nối một chiều từ ui đến vi.
Kết quả ghi rà file NET.OUT:
-          Dòng đầu ghi ra số nguyên K là kênh cần đổi hướng truyền tin.
Ví dụ:




NET.INP


NET.OUT




6 9
1 6
1 2
2 3
3 4
4 1
4 6
6 3
2 5
5 3
5 6


3




giải thích: Cần đổi chiều 3 kênh là thứ tự 1 7 và 9