彼得·潘（Peter Pan）接受了职业生涯规划指导，以帮助他确定未来的职业。由于他不想长大，他逃跑并前往梦幻岛（Neverland）寻求庇护。

梦幻岛有两条自西向东流淌的河流。在第一条河的岸边有 $a$ 个城市，顺着河流的方向依次标记为 $1$ 到 $a$ 的正整数。类似地，在第二条河的岸边有 $b$ 个城市，顺着河流的方向依次标记为 $1$ 到 $b$。顺流而下，如果两个城市在同一条河上且满足 $i < j$，则可以从城市 $i$ 到达城市 $j$。

梦幻岛的居民计划建立 $m$ 条单向航线。已知第 $i$ 条航线连接第一条河的城市 $x_i$ 和第二条河的城市 $y_i$，但尚未决定其方向。梦幻岛的居民希望他们的城市之间尽可能连通。就在那时，彼得·潘意识到他想以规划航线方向为生。

如果可以从第一个城市到达第二个城市，反之亦然，则称这两个城市是连通的。在旅行时，允许同时使用航线和河流。彼得·潘希望确定航线的方向，以最小化“其中任意两个城市都不连通”的最大城市集合的大小。帮助彼得·潘确定如何规划航线方向，以及在这种情况下上述集合的大小。

输入格式

第一行包含正整数 $a$、$b$ 和 $m$（$1 \le a, b, m \le 200\,000$），分别表示第一条河上的城市数量、第二条河上的城市数量以及航线数量。

接下来的 $m$ 行中，第 $i$ 行包含两个正整数 $x_i$ 和 $y_i$（$1 \le x_i \le a, 1 \le y_i \le b$），表示一条连接第一条河的城市 $x_i$ 和第二条河的城市 $y_i$ 的航线。没有任意一对城市会被重复列出。

输出格式

第一行输出“其中任意两个城市都不连通”的最大城市集合的最小可能大小。

第二行输出一个由空格分隔的字符 0 或 1 组成的序列，表示航线的方向。字符 0 表示航线从第一条河起飞并在第二条河降落，反之 1 表示从第二条河起飞并在第一条河降落。如果有多组解，输出任意一组。

数据范围

样例

输入样例 1

5 3
4
1 2
2 3
3 1
5 3

输出样例 1

1
1 1 0 0

输入样例 2

6 6
4
1 2
3 2
4 3
5 6

输出样例 2

9
1 0 1 1

输入样例 3

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

输出样例 3

5
1 0 1 1 0 1 0

说明

样例 1 说明：

如果航线按照输出所示的方向设定，则可以从任意一个城市到达其他任意一个城市。因此，不包含任何一对连通城市的最大集合是一个单例集合（大小为 1）。例如，可以从第一条河的城市 5 出发到达第一条河的城市 1：

$5 \text{ (I)} \to 3 \text{ (II)} \to 2 \text{ (I)} \to 3 \text{ (I)} \to 1 \text{ (II)} \to 2 \text{ (II)} \to 1 \text{ (I)}$。