Giải bài trực tuyến

Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xm, các đỉnh của Y ký hiệu là y1, y2, ..., yn.
Một bộ ghép trên G là một tập các cạnh thuộc E đôi một không có đỉnh chung.

Yêu cầu: Hãy tìm bộ ghép cực đại (có nhiều cạnh nhất) trên G.

Chú ý : Dùng Eof chứ không dùng SeekEof.

Input

• Dòng 1: Chứa hai số m, n (1 ≤ m, n ≤ 100)
• Các dòng tiếp, mỗi dòng chứa hai số nguyên dương i, j cho biết thông tin về một cạnh (xi, yj) thuộc E.

Output

• Dòng 1: Ghi số cạnh trong bộ ghép cực đại tìm được (K).
• K dòng tiếp theo, mỗi dòng ghi thông tin về một cạnh được chọn vào bộ ghép cực đại: Gồm 2 số u, v thể hiện cho cạnh nối (xu, yv).

Example

Input:
4 5
1 1
1 4
2 1
2 2
2 4
3 2
3 3
4 2
4 3


Output:
4
1 1
2 4
3 3
4 2