Trường ta đã xây dựng được phong trào Flash Mob thu hút được đông đảo các bạn trẻ quan tâm. Trường có lớp được đánh số từ đến . Hàng tuần, đoàn trường tổ chức các trận thi đấu giữa các lớp. Lớp giữ cờ vô địch đầu năm nay là lớp có số thứ tự (lớp vô địch cuối cùng của năm trước). Hàng tuần có diễn ra các trận thi đấu, mỗi trận thi đấu giữa hai lớp, lớp nào thắng được lớp đang giữ cờ vô địch sẽ được giữ cờ vô địch. Từ đầu năm đến nay đã diễn ra trận đấu.
Yêu cầu: Cho biết và trận đấu đã diễn ra. Hãy xác định lớp đang giữ cờ vô địch và số lớp đã từng giữ cờ vô địch trong năm nay.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương là chỉ số lớp giữ cờ vô dịch đầu năm và là số trận đấu đã diễn ra từ đầu năm đến nay;
dòng tiếp theo, dòng thứ chứa hai số nguyên dương cho biết đã diễn ra trận đấu giữa lớp và (trong đó lớp thắng, các trận đấu được liệt kê theo đúng thứ tự đã diễn ra).
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Dữ liệu ra:
Ghi ra trên một dòng hai số nguyên là chỉ số lớp đang giữ cờ vô địch và số lớp đã giữ cờ vô địch trong năm nay.
Ví dụ:
Dữ liệu vào:
1 3
2 1
3 2
4 1
Dữ liệu ra:
3 3
Giải thích:
Sau trận đấu thứ nhất (lớp thắng lớp ), lớp giữ cờ vô địch;
Sau trận đấu thứ hai (lớp thắng lớp ), lớp giữ cờ vô địch;
Trận đấu thứ ba không ảnh hưởng đến lớp giữ cờ vô địch.
Vậy: Lớp đang giữ cờ vô địch là lớp và có lớp đã giữ cờ vô địch là .
