Có \(n\) nam sinh và \(m\) nữ sinh trong một trường học. Tuần tới, một buổi khiêu vũ của trường sẽ được tổ chức. Một cặp nhảy bao gồm một nam sinh và một nữ sinh, và có \(k\) cặp tiềm năng.

Nhiệm vụ của bạn là tìm ra số lượng cặp nhảy tối đa và chỉ ra cách đạt được con số này.

Input

• Dòng đầu tiên là ba số nguyên \(n, m\) và \(k\): số nam sinh, nữ sinh và các cặp tiềm năng. Các nam sinh được đánh số \(1,2,\ldots, n\) và các nữ sinh được đánh số \(1,2,\ldots, m\).
• \(k\) dòng tiếp theo mô tả các cặp tiềm năng. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): nam sinh a và nữ sinh b sẵn sàng nhảy cùng nhau.

Output

• Đầu tiên in một số nguyên \(r\): số lượng cặp nhảy tối đa. Sau đó, in \(r\) dòng mô tả các cặp. Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

• \(1 \le n, m \le 500\)
• \(1 \le k \le 1000\)
• \(1 \le a \le n\)
• \(1 \le b \le m\)

Example

3 2 4
1 1
1 2
2 1
3 1

2
1 2
3 1