22176_TaskScheduling

Nowadays, the Advance Chipset Manufactory (ACM) is becoming more and more famous and competitive in the global computer market, and keeps receiving orders from a great number of companies. Sometimes the orders from different companies may even come simultaneously, but due to the law of commercial security protection, ACM can only deal with at most one order at any time. That means ACM has to delay some of the orders and may even annoy some clients. That’s why ACM has asked you, a computer expert, to help it make a proper task schedule.

With the help of Client Resource Management (CRM) System, ACM has defined the following rules to determine the processing sequence of its orders:

First, to satisfy important clients as quickly as possible, ACM has defined a priority relation map on the client companies. For example, suppose in the relation map company A is prior to company B, then when their orders arrive simultaneously, the orders from A will always be finished before the orders from B. Of course if A is prior to B, B is prior to C, then A is also prior to C. And ACM has guaranteed that the relation map is valid, that means no two companies are prior to each other directly or indirectly.

Second, if two or more orders arriving at the same time are from the same company or companies without priority relation, then they can be finished in arbitrary sequence.

Now, ACM has n orders coming simultaneously, and its machine is ready. Your job is to generate a proper task schedule, so that the time for which the order finished in the last place has to wait is as short as possible. You may assume that in the entire process until the n-th order is finished, no new orders will come.

Input may have multiple test cases. The first line is a positive integer T, ( T ≤ 20 ), denoting the number of test cases followed. In each test case, the first line is three positive integer n, m, k ( 1 ≤ n, m ≤ 1000 ), n is the number of different orders coming simultaneously, m is the number of different clients and k is the number of client pairs having priority relations. The orders are numbered from 1 to n and the clients from 1 to m. Then k lines follow. Each line consists of two different integers x, y, ( 1 ≤ x, y ≤ m ), that means client x is prior to client y. And the last part of each case is n lines. Each line is the description of an order, including two positive integers, ci and ti , ( 1 ≤ ci ≤ m, 1 ≤ ti ≤ 10000, for each i, 1 ≤ i ≤ n ). ci is the company number of the i-th order, and ti is the time needed to finish the i-th order.

For each test case, the output should be one single line consisting of n+1 integers separated by white spaces. The first integer indicates the minimum time that the last order has to wait for. And the other n integers should be a permutation of integers 1 to n, denoting the processing sequence of those n orders. There may be multiple possible answers, just output any one of them.

1
3 2 1
2 1
1 100
2 100
2 100

200 2 3 1