Sau khi hoàng tử lên ngôi, nhà vua quyết định xây dựng lại kinh đô. Tể tướng trình lên một bản đồ quy hoạch của kinh đô mới có địa điểm đánh số từ tới và con đường đánh số từ tới . Con đường thứ nối giữa hai điểm và cho phép đi lại giữa hai địa điểm đó theo cả hai chiều. Trong bản đồ quy hoạch, giữa một cặp địa điểm có thể có nhiều con đường nối chúng, có thể có con đường nối một địa điểm với chính nó, và sự đi lại giữa một vài cặp địa điểm có thể không thực hiện được.
Mặc dù có rất nhiều thứ phải điều chỉnh trong bản đồ quy hoạch, do rất bận nên nhà vua tạm xử lý chỉ một vấn đề: Xây dựng thêm đúng một con đường để giảm thiểu số con đường độc đạo trong bản đồ. (Ta gọi một con đường nối giữa hai địa điểm gọi là độc đạo nếu như con đường đó bị cấm để tổ chức lễ hội thì sẽ không có cách nào đi từ địa điểm sang địa điểm bằng những con đường khác).
Yêu cầu: Hãy giúp nhà vua lên phương án xây dựng con đường mới và cho biết số lượng con đường độc đạo bị giảm đi theo phương án xây dựng. Con đường mới có thể đi song song với một con đường đã có trong quy hoạch, tức là có thể cho nối giữa hai địa điểm đã có con đường nối chúng trong quy hoạch cũ.
Dữ liệu:
Dòng đầu chứa hai số nguyên ;
dòng tiếp theo, dòng thứ chứa hai số nguyên dương , các số trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả:
Ghi ra một số nguyên duy nhất là số lượng con đường độc đạo bị giảm đi theo phương án xây dựng, ghi số nếu số con đường độc đạo không thể giảm đi.
