Alan muốn tô màu cho các cạnh của đồ thị hai phía sao cho sử dụng ít màu nhất có thể, sao cho không có hai cạnh cùng màu chia sẻ một đỉnh nào. Goran đã cho anh ta một đồ thị hai phía và yêu cầu anh ta giải quyết vấn đề này.

Goran đã đề xuất cho Alan một cách tiếp cận sử dụng một dải vô hạn. Tuy nhiên, khi nhận ra rằng điều đó có vẻ quá phức tạp, Goran đã giảm bớt yêu cầu bằng cách cho phép Alan sử dụng không quá ~X~ màu, với ~X~ là lũy thừa nhỏ nhất của ~2~ không nhỏ hơn số màu cần thiết để tô màu đồ thị (đã được gọi là C).

Hãy giúp Alan giải quyết bài toán.

Input

• Dòng đầu tiên chứa ba số nguyên dương: ~L, R~ và ~M~ ~(1 \leq L, R \leq 100,000, 1 \leq M \leq 500,000)~, lần lượt là số đỉnh ở một bên của đồ thị hai phía, số đỉnh ở bên kia của đồ thị hai phía và số cạnh của đồ thị.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a_i~ ~(1 \leq a_i \leq L)~ và ~b_i~ ~(1 \leq b_i \leq R)~ đại diện cho một cạnh giữa đỉnh thứ ~a_i~ từ bên thứ nhất và đỉnh thứ ~b_i~ từ bên thứ hai của đồ thị hai phía. Tất cả các cặp ~(a_i, b_i)~ sẽ là duy nhất.

Onput

• Trên dòng đầu tiên, xuất một số nguyên dương ~K~, là số màu sử dụng.
• Trong ~M~ dòng tiếp theo, xuất một số nguyên dương ~c_i~ ~(1 \leq c_i \leq K)~, nhãn của màu của cạnh thứ ~i~.

Chú ý

• ~20 \%~ tổng số điểm, sẽ thỏa mãn điều kiện ~L, R \leq 100~.
• ~20 \%~ tổng số điểm bổ sung, sẽ thỏa mãn điều kiện ~L, R \leq 5000~.

Sample Input 1

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

Sample Output 1

2
1
2
1
2
1

Sample Input 2

2 4 4
1 1
1 2
1 3
2 4

Sample Output 2

4
1
2
3
4

Giải thích

Trong test thứ hai, số màu tối thiểu cần là 3. Tuy nhiên, việc sử dụng 4 màu cũng là chấp nhận được vì đó là lũy thừa nhỏ nhất của 2 mà không nhỏ hơn 3.