题目内容

某外卖站点当天只派一名骑手出站。有 $n$ 个订单，编号 $1 \sim n$。骑手同一时刻只能配送一单，从时刻 $0$ 开始连续工作，两单之间没有额外空闲时间。第 $i$ 个订单的配送耗时为 $t_i$，客户要求的最迟送达时刻为 $d_i$。骑手一旦开始配送某单就必须做到结束，该单完成时刻为开始时刻加上 $t_i$，必须不超过 $d_i$。

订单之间还有两类约束：

1. 出餐依赖：共 $m$ 条。一条依赖 $u\ v$ 表示必须先完成订单 $u$，才能开始订单 $v$，中间可以插入其他订单。
2. 同址套餐：共 $k$ 条链。一条链给出若干订单的固定顺序，这些订单必须按该顺序连续配送，中间不能插入任何其他订单。每个订单最多出现在一条链中。

请给出一个完成全部订单的配送顺序，并同时满足：

• 依赖与套餐都不被破坏；
• 每一单的完成时刻都不超过自己的截止时刻；
• 若有多种合法顺序，输出订单编号序列字典序最小的那一种。

若把依赖和套餐的先后关系合在一起后出现环形等待(即有环)，输出 $-1$。例如套餐链要求先 $a$ 后 $b$，同时又有依赖要求先 $b$ 后 $a$。不存在环、但任何顺序都会导致至少一单超时，输出 $-2$。

输入描述

第一行三个整数 $n$、$m$、$k$。

接下来 $n$ 行，第 $i$ 行两个整数 $t_i$、$d_i$。

接下来 $m$ 行，每行两个整数 $u$、$v$，表示必须先完成 $u$ 再开始 $v$。

接下来 $k$ 行，每行先给出一个整数 $L$（$L \ge 2$），再给出 $L$ 个订单编号，表示一条套餐链，必须按从左到右的顺序连续配送。

约束

$1 \le n \le 100$

$0 \le m \le 5000$

$0 \le k \le n$

$1 \le t_i \le 1000$

$1 \le d_i \le 10^9$

$1 \le u,v \le n$，$u \ne v$

$2 \le L \le n$

套餐链两两不相交，链内编号互不相同，编号都在 $1 \sim n$ 内

输出描述

若存在环形等待，输出 $-1$。

若无环但无法让全部订单在截止前送达，输出 $-2$。

否则输出一行 $n$ 个整数，表示字典序最小的合法配送顺序，数字之间用空格分隔。

样例1

输入

4 0 1
3 10
3 6
1 4
1 100
2 3 4

输出

2 3 4 1

说明

没有出餐依赖。套餐链要求订单 $3$ 送完后必须紧接着送订单 $4$。

按编号从小到大的 $1\ 2\ 3\ 4$，完成时刻为 $3$、$6$、$7$、$8$，订单 $3$ 在时刻 $7$ 才完成，超过 $4$。把 $1$ 插在 $3$ 和 $4$ 中间得到 $2\ 3\ 1\ 4$，字典序更小，但破坏了套餐必须连续。

合法顺序有 $2\ 3\ 4\ 1$（完成时刻 $3$、$4$、$5$、$8$）和 $3\ 4\ 2\ 1$（完成时刻 $1$、$2$、$5$、$8$）。前者字典序更小。

样例2

输入

2 2 0
1 10
1 10
1 2
2 1

输出

-1

说明

订单 $1$ 必须在 $2$ 前，订单 $2$ 又必须在 $1$ 前，形成环形等待，输出 $-1$。