Background

BiLeo 正在调试一台旧式演出控制台。

Description

控制台左侧有 $n$ 个信号源模块，编号为 $1\sim n$；右侧有 $m$ 个接入端口，编号为 $1\sim m$。

并不是每个信号源模块都能接入任意端口。经过测试，BiLeo 记录下了若干条“可正常接入”的记录：如果第 $a$ 个信号源模块可以接入第 $b$ 个端口，就会给出一条记录 $(a,b)$。

现在 BiLeo 希望同时启用尽可能多的信号源模块，使每个被启用的模块都接入一个可用端口。

但是由于硬件限制：

• 每个信号源模块最多接入一个端口；
• 每个接入端口最多连接一个信号源模块。

请你求出最多能成功接入多少个信号源模块，并输出任意一种最优方案。

对于方案中的第 $i$ 个数字：

• 若第 $i$ 个信号源模块接入了某个端口，则输出该端口编号；
• 若第 $i$ 个信号源模块未被启用，则输出 $0$。

Format

Input

第一行包含三个整数 $n,m,q$，分别表示信号源模块数量、接入端口数量以及可正常接入的记录条数。

接下来 $q$ 行，每行两个整数 $a,b$，表示第 $a$ 个信号源模块可以接入第 $b$ 个端口。

数据保证：

$$1 \le a \le n,\qquad 1 \le b \le m$$ $$1 \le n,m \le 5\times 10^4,\qquad 0 \le q \le 2\times 10^5$$

且不会出现重复的记录。

Output

第一行输出一个整数，表示最多能成功接入的信号源模块数量。

第二行输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个信号源模块最终接入的端口编号；如果没有接入任何端口，则输出 $0$。

Samples

2 2 3
1 1
1 2
2 1

2
2 1

2 2 2
1 1
2 1

1
1 0

Limitation

1s, 1024KiB for each test case.