题目描述

译自 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$。

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

数据范围与提示

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