3957: day4T3

## T3 (TL=2s)

#### 题目描述

有两组人在抢一块金条。两个组编号为 $1$ 和 $2$ ，$1$ 组的人从 $1$ 到 $n$ 编号，$2$ 组的人从 $1$ 到 $m$ 编号。

初始时，$P$ 组的 $X$ 号人拿着金条，然后争夺之战一触即发。

在一轮中：

没拿金条的那组的所有**还在场的**人按照编号顺序由小到大进行决策：

1. 不去抢。此时什么事也不会发生，决策权给到下一个人。
2. 去抢。那么金条到他手里，原本持有金条的人遗憾离场，游戏立即进入下一轮。

如果编号最大的人都决策完了后金条还没被抢到，那么金条就归拿着的人所有了。

两组之间有 $k$ 对人有私交，他们不会在任何情况下直接去抢对方手里的金条。

但一个人对于和他没有私交的人就可以任意决策。

每个人都第一希望拿到金条，在拿不到金条的情况下，他们第二希望不遗憾离场。

如果所有人都绝顶聪明，问最后每个人的情况是什么？（情况分为三种：遗憾离场，在场但无金条，得到金条）

#### 输入格式

第一行五个整数 $n,m,P,X,k$ 。

接下来 $k$ 行每行两个整数 $a_i,b_i$ ，表示 $1$ 组的 $a_i$ 号人和 $2$ 组的 $b_i$ 号人有私交。

保证不存在两行描述一组相同的关系（即 $a_i=a_j,b_i=b_j$）。

#### 输出格式

第一行 $n$ 个用空格分隔的数字，表示 $1$ 组每个人的最终情况。

第二行 $m$ 个用空格分隔的数字，表示 $2$ 组每个人的最终情况。

每个情况用一个数字表示，遗憾离场为 $0$ ，在场但无金条为 $1$ ，得到金条为 $2$ 。

#### 样例输入 1

```
2 1 1 1 0
```

#### 样例输出 1

```
2 1
1
```

#### 样例输入 2

```
2 1 1 1 1
2 1
```

#### 样例输出 2

```
0 1
2
```

#### 样例输入 3

```
2 2 1 1 1
2 2
```

#### 样例输出 3

```
0 1
1 2
```

#### 样例解释

对于样例1，由于1组有两个人，2组只有一个，因此2组的那个人不敢来抢1组1号的金条（因为抢完还得在被1组的2号抢回去后遗憾离场）。

对于样例2，由于2组的1号和1组的2号有私交，所以他能抢1组1号的金条。

#### 数据范围

本题开启捆绑测试。

Subtask 1 (20pts)，满足 $k=0$ 。

Subtask 2 (20pts)，满足 $n,m\leq 5$ 。

Subtask 3 (20pts)，满足 $n,m\leq 10$ 。

Subtask 4 (20pts)，满足 $n,m\leq 50$ 。

Subtask 5 (20pts)，无特殊限制。

对于全部数据，满足 $n,m\leq 1000,k\leq n\times m$ 。

提示：本题输入量较大，建议使用效率较高的读入方式。