Goblins And Gnomes

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

城市由 $n$ 个大厅和 $m$ 条单向隧道组成，隧道图是有向无环图。共有 $k$ 波进攻，第 $i$ 波有 $i$ 个哥布林。每个哥布林选择一条有向路径，不同哥布林的路径不能经过同一个大厅；他们会让被经过的大厅总数最大。如果能覆盖全部大厅，Monocarp 失败。

在第 $i$ 波前准备 $t_i$ 分钟可获得 $\max(0,x_i-t_i y_i)$ 分。每分钟可以永久执行一次以下封锁操作：封锁某个大厅的全部出边，或封锁某个大厅的全部入边。

请输出能够通过全部波次且总分最大的任意策略。

输入格式

第一行包含 $n,m,k$。接下来 $m$ 行给出有向隧道，随后 $k$ 行给出 $x_i,y_i$。

输出格式

先输出操作总数 $a$，再输出 $a$ 个整数。正整数 $v$ 表示封锁大厅 $v$ 的全部出边，负整数 $-v$ 表示封锁大厅 $v$ 的全部入边，$0$ 表示召唤下一波。

非零操作不能重复，必须恰好输出 $k$ 个零。若有多种最优策略，输出任意一种。

样例输入 1

5 4 4
1 2
2 3
4 3
5 3
100 1
200 5
10 10
100 1

样例输出 1

6
-2 -3 0 0 0 0

样例输入 2

5 4 4
1 2
2 3
4 3
5 3
100 100
200 5
10 10
100 1

样例输出 2

6
0 -3 0 0 1 0

样例输入 3

5 10 1
1 2
1 3
1 4
1 5
5 2
5 3
5 4
4 2
4 3
2 3
100 100

样例输出 3

6
1 2 3 4 5 0

数据范围

$2\le n\le50$，$0\le m\le n(n-1)/2$，$1\le k<n$，$1\le x_i,y_i\le10^9$。