ストーリー

F社のプロジェクトリーダーに就任したあなたの仕事は、チームメンバーに適切にタスクを割り振ることである。 現在取り組んでいるプロジェクトはいくつかのタスクからなり、 各チームメンバーの持つ技能レベルと各タスクごとの要求技能レベルに応じて、タスクの完了までにかかる日数の期待値が変化する。 経験豊富なあなたは、各タスクの要求技能レベルを正確に把握することが出来るが、就任したばかりのため、各チームメンバーの技能レベルはまだ全く分かっていない。 チームメンバーの技能レベルを徐々に見極めながら、適切にタスクを割り振ってほしい。

問題文

$N$ 個のタスクを $M$ 人のチームメンバーに割り振りたい。 各タスクは高々1人に割り振り、タスクが割り振られたチームメンバーにはそのタスクが完了するまで他のタスクを割り振ることは出来ない。 全部で $K$ 種類の技能があり、各チームメンバー $j$ には技能レベルを表す非負整数ベクトル $\\bm{s_j} = (s_{j,1},\\cdots,s_{j,K})$ が、各タスク $i$ には要求技能レベルを表す非負整数ベクトル $\\bm{d_i} = (d_{i,1},\\cdots,d_{i,K})$ がそれぞれ定まっている。 このうち、各チームメンバーの技能レベル $\\bm{s_1},\\cdots,\\bm{s_M}$ は入力として与えられない。

$w_{i,j}:=\\sum_{k=1}^K \\max(0,d_{i,k}-s_{j,k})$ と定める。 チームメンバー $j$ にタスク $i$ を割り振った時、タスクの完了までには以下のように定める $t_{i,j}$ 日かかる。

1. $w_{i,j}=0$ の場合、$t_{i,j}=1$。
2. $w_{i,j}>0$ の場合、$\-3$ 以上 $3$ 以下の整数値をとる一様乱数を $r_i$ として、$t_{i,j}=\\max(1,w_{i,j}+r_i)$。

$t$ 日かかるタスクを $d$ 日目に開始した場合、$d+t-1$ 日目の終わりにそのタスクは完了する。 タスク間には依存関係があり、あるタスクを開始するためには、依存する全てのタスクが前日の終わりまでに完了していなければならない。 出来るだけ短い日数で全てのタスクを完了してほしい。

入出力

各入力値の範囲については入力生成の項を参照せよ。

まずはじめに、タスク数 $N$、チームメンバー数 $M$、技能数 $K$、依存関係数 $R$、各タスクの要求技能レベル $\\bm{d_1},\\cdots,\\bm{d_N}$、依存するタスクの組のリスト $(u_1,v_1),\\cdots,(u_R,v_R)$ が以下の形式で標準入力から与えられる。

$N$ $M$ $K$ $R$ $d_{1,1}$ $\\cdots$ $d_{1,K}$ $\\vdots$ $d_{N,1}$ $\\cdots$ $d_{N,K}$ $u_1$ $v_1$ $\\vdots$ $u_R$ $v_R$

$(u_i,v_i)$ は、タスク $v_i$ ($1\\leq v_i\\leq N$) がタスク $u_i$ ($1\\leq u_i\\leq N$) に依存しており、$v_i$ を開始する前に $u_i$ を完了しなければならないことを示している。 $u_i<v_i$ を満たし、同じ$(u_i,v_i)$のペアは高々一回しか入力に含まれない。

次に、1日目から始め、毎日以下の2つの処理をせよ。

まず、その日にタスクを開始するチームメンバー $a_i$ ($1\\leq a_i\\leq M$) と担当するタスク $b_i$ ($1\\leq b_i\\leq N$) の組のリスト $(a_1,b_1),\\cdots,(a_m,b_m)$ を以下の形式で標準出力に1行に出力せよ。

$m$ $a_1$ $b_1$ $\\cdots$ $a_m$ $b_m$

**出力のあとは標準出力を flush しなければならない。**そうしない場合、TLE