Trong ngày hội thể thao văn hoá tại sân vân động trung tâm thành phố sẽ có một trận đấu bóng đá của đội CHAMPION gặp đội ngôi sao thành phố và một buổi biểu diễn của dàn nhạc nổi tiếng OLIMPIAD. Vé vào xem sẽ được phát cho từng cá nhân của các tập thể có nhiều thành tích trong phong trào thể thao văn hoá, mỗi tập thể được phát một loại vé, trên vé có ghi tên cụ thể để phục vụ cho việc giữ gìn an ninh trật tự.
Tập thể sinh viên của một trường gồm người nhận vé xem bóng đá, nhưng tất cả lại muốn đi xem ca nhạc. Rất may là Ban tổ chức cho phép tập thể đổi vé theo hình thức sau: những người có vé phải tham gia một số công việc chuẩn bị, mỗi công việc cần đúng người thực hiện. Sau khi hoàn thành công việc, ai có vé xem bóng đá được đổi thành vé xem ca nhạc và ngược lại, ai có vé xem ca nhạc được đổi thành vé vào xem bóng đá. Trưởng đoàn sinh viên quyết định tổ chức cho các bạn đi lao động và đổi vé. Sau khi các bạn đó về lại tổ chức nhóm khác đi đổi. Một người có thể tham gia đổi vé nhiều lần nếu cần, nhưng không được đi đổi vé hộ người khác.
Yêu cầu: Hãy xác định tối thiểu phải tổ chức bao nhiêu nhóm đi lao động đổi vé để tất cả thành viên của tập thể đều đổi được vé đi xem ca nhạc hoặc cho biết không có cách thực hiện được điều đó.
Dữ liệu vào:
Gồm nhiều dòng (không quá dòng), mỗi dòng hai số nguyên cách nhau ít nhất một dấu cách, mỗi dòng tương ứng với một trường hợp cần xử lý .
Dữ liệu ra:
Mỗi dòng là một số nguyên - số lần đi đổi vé, ứng với một cặp của dữ liệu vào, trong trường hợp không có cách đổi vé cho tất cả mọi người.
