Light Cover - Weekly Challenge 1: Approximation | Repovive

W1D3B. Light Cover

2 pts1s256 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$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

W1D3B. Light Cover

Constraints

Input

Output

Samples

W1D3B. Light Cover

Constraints

Input

Output

Samples