当前没有测试数据。

题目描述
译自 COCI 2021/2022 Contest #5 T5「Usmjeravanje」

在 Neverland 上有两条河，第一条河边坐落着 $a$ 个城市，从上游到下游按 $1$ 到 $a$ 编号，第二条河边坐落着 $b$ 个城市，从上游到下游按 $1$ 到 $b$ 编号。

对于同一条河边的城市 $i,j$，如果 $i<j$，那么可以从城市 $i$ 乘船到城市 $j$。

Neverland 的人们计划建立 $m$ 条单行航道，每一条航道都是连接第一条河边的城市 $a_i$ 和第二条河边的城市 $b_i$，但是，方向并未确定。

一对城市 $(x,y)$ 被称为连通，当且仅当存在一种从 $x$ 到 $y$ 的路线，也存在一种从 $y$ 到 $x$ 的路线。

你定义了一个权值为不存在城市连通的城市集合的最大大小。现在你想给航道定向使得这个权值最小。

---

输入格式
第一行三个整数 $a,b,m$。
接下来 $m$ 行，每行两个整数 $a_i,b_i$。

---

输出格式
第一行一个整数，表示你最小化的权值。
第二行 $m$ 个在 $[0,1]$ 内的整数，表示你的定向，如果你想要让 $a_i$ 到 $b_i$，输出 $0$，否则输出 $1$。

---

样例 1
输入：

5 3
4
1 2
2 3
3 1
5 3

输出：

1
1 1 0 0

在构造的方案下，对于每一对点，他们都是相互可达的，所以权值最小为 $1$。

---

样例 2
输入：

6 6
4
1 2
3 2
4 3
5 6

输出：

9
1 0 1 1

---

样例 3
输入：

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

---

数据范围与提示
对于全部数据，$1 \le a,b,m \le 2 \times 10^5$，$1 \le a_i \le a$，$1 \le b_i \le b$。

Subtask 编号	特殊限制	分值
1	$a,b,m \le 15$	20
2	$a,b \le 10^3$	30
3		60