Problem Description

Neverland has two rivers. Along each river there are several cities, with the numbers of cities being $a$ and $b$, respectively.

For two cities $i, j$ on the same river, if $i \lt 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 shipping routes connecting city $x_i$ on the first river and city $y_i$ on the second river, but the direction is still to be determined.

If two cities can reach each other via waterways or shipping routes, then they are said to be connected. Among all cities, there are some sets of cities such that no pair of cities in the same set is connected. Please choose a direction for each shipping route so that, among all such sets, the maximum size of a set is as small as possible.

Input Format

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

The second line contains one positive integer $m$.

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

Output Format

The first line contains one positive integer, the minimum possible value of the maximum set size.

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

If there are multiple valid solutions, output any one.

5 3
4
1 2
2 3
3 1
5 3

1
1 1 0 0

6 6
4
1 2
3 2
4 3
5 6

9
1 0 1 1

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

5
1 0 1 1 0 1 0

Hint

[Sample 1 Explanation]

An optimal solution can make every pair of cities connected, so the answer is $1$.

[Constraints]

This problem uses bundled tests.

• 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 testdata, $1 \le a, b, m \le 2 \times 10^5$, $1 \le x_i \le a$, $1 \le y_i \le b$.

[Notes]

This problem uses a self-written Special Judge. If you have any questions about it or want to hack, please PM the author or make a post.

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

Translated by ChatGPT 5