Usmjeravanje

문제

Peter Pan was given career guidance to help determine his future profession. As he does not want to grow up, he ran away and sought shelter in Neverland. There are two rivers in Neverland, flowing from west to east. On the shore of the first river, there are $aa$ cities, labeled with positive integers from $11$ to $aa$ in the same direction that the river flows. Similarly, on the shore of the second river there are $bb$ cities labeled in the same direction from $11$ to $bb$. Traveling downstream, it’s possible to reach city $jj$ from city $ii$ if both of these cities are on the same river and if .

Citizens of Neverland plan to establish $mm$ one-way flight routes. It is given that the $ii$-th route should connect city $x_{i}x\_i$ from the first river and city $y_{i}y\_i$ from the second river, but it has not yet been decided in which direction. The citizens of Neverland would like their cities to be as connected as possible. At that moment Peter Pan realized that he would like to direct flight routes for a living.

A pair of cities is called connected if it is possible to reach the second city starting from the first, and vice versa. While traveling, it is allowed to use both flight routes and rivers. Peter Pan wants to determine the route directions in order to minimize the largest set of cities in which no pair of cities is connected. Help Peter Pan and determine how to direct the routes and what would the size of the mentioned set be in that case.

입력

The first line contains positive integers $aa$, $bb$ and $mm$ (1 ≤ a, b, m ≤ 200\,000), the number of cities on the first river, the number of cities on the second river and the number of flight routes, respectively.

The $ii$-th of the next $mm$ lines contains two positive integers $x_{i}x\_i$ and $y_{i}y\_i$ (1 ≤ x_i ≤ a, 1 ≤ y_i ≤ b) which denote a flight route connecting city $x_{i}x\_i$ from the first river and city $y_{i}y\_i$ from the second river. No pair of cities is listed more than once.

출력

In the first line print the least possible size of the maximum set of cities in which no pair of cities is connected.

In the second line print a sequence of characters 0 or 1 separated by spaces which denote the directions of the flight routes. The character 0 means that the flight takes off from the first river and lands on the second river, and conversely for 1. If there is more than one solution, output any.

힌트

Clarification of the first example:

If the flights are directed as shown in the output, it is possible to reach any city starting from any other city. Therefore, the largest set containing no pair of connected cities is a singleton. For example, it’s possible to reach city 1 from the first river by starting from city 5 from the first river:

5 (I) → 3 (II) → 2 (I) → 3 (I) → 1 (II) → 2 (II) → 1 (I).

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