Light Cover - Testing Approx Problems | Repovive

1012D. Light Cover

1s256 MB

You are given a bipartite graph. The graph has $L$ vertices on the left side and $R$ vertices on the right side.

The vertices are numbered from $1$ to $L+R$ . Vertices $1,2,\ldots,L$ are on the left side, and vertices $L+1,L+2,\ldots,L+R$ are on the right side.

Each vertex $i$ has a positive weight $w_i$ .

A set of vertices is called a cover if every edge has at least one endpoint in the set.

The weight of a cover is the sum of weights of its vertices. Let $OPT$ be the minimum possible weight of a cover.

You do not need to find an optimal cover. You only need to output any cover whose weight is at most twice $OPT$ .

In other words, if the weight of your cover is $W$ , your output is accepted if $W \le 2 \times OPT$ .

Constraints

$1 \le t \le 5$
$1 \le L,R$
$L+R \le 10^5$
$0 \le m \le 5 \times 10^5$
The sum of $L+R$ over all test cases is at most $10^5$
The sum of $m$ over all test cases is at most $5 \times 10^5$
$1 \le w_i \le 10^9$
Each edge connects one left vertex to one right vertex
There are no duplicate edges

Input

The input is given in the following format:

t

\left. \begin{array}{l} L \quad R \quad m \\ w_1 \quad w_2 \quad \cdots \quad w_{L+R} \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

For each edge, $1 \le u_i \le L$ and $L+1 \le v_i \le L+R$ .

Output

For each test case, first output an integer $k$ , the number of vertices in your cover.

Then output $k$ distinct integers $x_1,x_2,\ldots,x_k$ , the vertices you choose.

The chosen vertices must form a cover. If the weight of your cover is $W$ , it must satisfy $W \le 2 \times OPT$ .

The output format is:

\left. \begin{array}{l} k \\ x_1 \quad x_2 \quad \cdots \quad x_k \end{array} \right\} \times t

If $k=0$ , the second line for that test case may be empty.

Samples

Input

1
3 3 5
4 3 6 2 5 4
1 4
1 5
2 5
3 5
3 6

Explanation

The chosen vertices cover all edges: every edge has its left endpoint among $1,2,3$ .

The total weight is $4+3+6=13$ .

The minimum possible cover weight is $11$ . For example, $\{4,5,6\}$ is a cover with total weight $2+5+4=11$ . The shown output is not optimal, but $13 \le 2 \times 11$ .

Output

3
1 2 3

You are given a bipartite graph. The graph has $L$ vertices on the left side and $R$ vertices on the right side.

The vertices are numbered from $1$ to $L+R$ . Vertices $1,2,\ldots,L$ are on the left side, and vertices $L+1,L+2,\ldots,L+R$ are on the right side.

Each vertex $i$ has a positive weight $w_i$ .

A set of vertices is called a cover if every edge has at least one endpoint in the set.

The weight of a cover is the sum of weights of its vertices. Let $OPT$ be the minimum possible weight of a cover.

You do not need to find an optimal cover. You only need to output any cover whose weight is at most twice $OPT$ .

In other words, if the weight of your cover is $W$ , your output is accepted if $W \le 2 \times OPT$ .

$1 \le t \le 5$
$1 \le L,R$
$L+R \le 10^5$
$0 \le m \le 5 \times 10^5$
The sum of $L+R$ over all test cases is at most $10^5$
The sum of $m$ over all test cases is at most $5 \times 10^5$
$1 \le w_i \le 10^9$
Each edge connects one left vertex to one right vertex
There are no duplicate edges

The input is given in the following format:

t

\left. \begin{array}{l} L \quad R \quad m \\ w_1 \quad w_2 \quad \cdots \quad w_{L+R} \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

For each edge, $1 \le u_i \le L$ and $L+1 \le v_i \le L+R$ .

For each test case, first output an integer $k$ , the number of vertices in your cover.

Then output $k$ distinct integers $x_1,x_2,\ldots,x_k$ , the vertices you choose.

The chosen vertices must form a cover. If the weight of your cover is $W$ , it must satisfy $W \le 2 \times OPT$ .

The output format is:

\left. \begin{array}{l} k \\ x_1 \quad x_2 \quad \cdots \quad x_k \end{array} \right\} \times t

If $k=0$ , the second line for that test case may be empty.

The chosen vertices cover all edges: every edge has its left endpoint among $1,2,3$ .

The total weight is $4+3+6=13$ .

The minimum possible cover weight is $11$ . For example, $\{4,5,6\}$ is a cover with total weight $2+5+4=11$ . The shown output is not optimal, but $13 \le 2 \times 11$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1012D. Light Cover

Constraints

Input

Output

Samples

1012D. Light Cover

Constraints

Input

Output

Samples