Problem Description

Neverland has two rivers. Each river has several cities along its banks, with the numbers of cities being $a$ and $b$ respectively.

For two cities $i$ and $j$ located along the same river, if $i < j$, then it is possible to travel by water from city $i$ to city $j$.

The residents of Neverland have decided to build $m$ one-way air routes connecting city $x_i$ on the first river to city $y_i$ on the second river, but the directions need to be determined.

Two cities are considered connected if they can reach each other either by water or by air routes. Among all cities, there are several sets such that no pair of cities within the same set are connected. Please choose a direction for each air route to minimize the size of the largest set.

Input Format

The first line contains two positive integers $a$ and $b$.

The second line contains one positive integer $m$.

The next $m$ lines each contain two positive integers $x_i$ and $y_i$, representing a one-way air route connecting city $x_i$ on the first river to city $y_i$ on the second river. The data guarantees that there are no duplicate unordered pairs $(x_i, y_i)$.

Output Format

The first line contains one positive integer, representing the minimum size of the largest set.

The second line contains $m$ integers, either $0$ or $1$. Here, $0$ indicates the direction from city $x_i$ on the first river to city $y_i$ on the second river, and $1$ indicates the opposite direction.

If there are multiple valid solutions, output any one of them.

Sample Input and Output

Sample Input #1

5 3
4
1 2
2 3
3 1
5 3

Sample Output #1

1
1 1 0 0

Sample Input #2

6 6
4
1 2
3 2
4 3
5 6

Sample Output #2

9
1 0 1 1

Sample Input #3

8 7
7
1 3
2 1
3 4
5 6
6 5
6 7
8 7

Sample Output #3

5
1 0 1 1 0 1 0

Notes

[Sample 1 Explanation]

The optimal solution ensures that every pair of cities is connected, thus the answer is $1$.

[Data Range and Constraints]

This problem is bundled test cases.

• Subtask 1 (20 pts): $1 \le a, b, m \le 15$.
• Subtask 2 (30 pts): $1 \le a, b \le 1000$.
• Subtask 3 (60 pts): No additional constraints.

For $100\%$ of the data, $1 \le a, b, m \le 2 \times 10^5$, $1 \le x_i \le a$, $1 \le y_i \le b$.

[Source] COCI 2021-2022#5 Task 5 Usmjeravanje.

见题面 Input 部分

见题面 Output 部分