{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"在一台机器上有n个抢先作业要处理。每个作业j有一个处理时间pj和最后期限dj。抢占约束由无圈的有向图指定。图中的弧(i,j)表示作业i必须在作业j之前处理。解决方案由作业序列指定。对于任何解决方案,完成时间Cj都很容易确定。\n目标是寻找最优解以使最小化\n最大{Cj-dj,0}。"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含单个整数n,1 ≤ n ≤ 50000。接下来的n行中的每一行包含两个整数pj和dj,0 ≤ pj ≤ 1000,0 ≤ dj ≤ 1000000,由一个或多个空格分隔。行n + 2包含整数m(弧数),0 ≤ m ≤ 10*n。接下来的m行中的每一行包含两个整数i和j,1 ≤ i,j ≤ n。"}},{"title":"Output","value":{"format":"HTML","content":"n行中的每一行都包含整数i(最佳序列中的作业数)。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\n4 1\n4 0\n1\n1 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e1\n2\u003c/pre\u003e"}}]}