Các Cặp Tương Thích

Có $n$ thành viên ở nhóm trái và $m$ thành viên ở nhóm phải. Danh sách $k$ cặp được cho biết trước; cặp $(u,v)$ nghĩa là thành viên $u$ của nhóm trái có thể làm việc cùng thành viên $v$ của nhóm phải.

Hãy chọn nhiều cặp tương thích nhất sao cho không thành viên nào xuất hiện trong hai cặp được chọn. Ngoài số lượng tối đa, bạn phải in ra một cách chọn đạt được số lượng đó.

Input

• Dòng đầu chứa ba số nguyên $n,m$ và $k$.
• Mỗi dòng trong $k$ dòng tiếp theo chứa hai số nguyên $u$ và $v$, mô tả một cặp tương thích. Thành viên nhóm trái được đánh số từ $1$ đến $n$, thành viên nhóm phải được đánh số từ $1$ đến $m$.

Output

• Dòng đầu in số nguyên $r$, là số cặp lớn nhất có thể chọn.

• Trong $r$ dòng tiếp theo, mỗi dòng in một cặp $u$ $v$ được chọn. Các cặp phải có trong danh sách đầu vào; mọi chỉ số ở mỗi phía phải đôi một khác nhau.

• Nếu có nhiều phương án tối ưu, bạn có thể in bất kỳ phương án nào.

Constraints

• $1\le n,m\le 500$.
• $0\le k\le 1000$.
• Mỗi cặp đầu vào thỏa $1\le u\le n,1\le v\le m$.
• Không có cặp nào xuất hiện hai lần trong input.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 10$ và $k\le 40$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 4 5
1 1
1 2
2 1
3 3
4 3

3
1 2
2 1
3 3