Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  1. Contests
  2. Weekly Challenge 1: Approximation
  3. W1D3B

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D3B. Light Cover

2 pts·1s·256 MB

Constraints

Input

Output

Samples

Input
1
3 3 5
4 3 6 2 5 4
1 4
1 5
2 5
3 5
3 6
Explanation
Output
3
1 2 3

You are given a bipartite graph. The graph has LLL vertices on the left side and RRR vertices on the right side.

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

Each vertex iii has a positive weight wiw_iwi​.

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 OPTOPTOPT 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 OPTOPTOPT.

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

  • 1≤t≤51 \le t \le 51≤t≤5
  • 1≤L,R1 \le L,R1≤L,R
  • L+R≤105L+R \le 10^5L+R≤105
  • 0≤m≤5×1050 \le m \le 5 \times 10^50≤m≤5×105
  • The sum of L+RL+RL+R over all test cases is at most 10510^5105
  • The sum of mmm over all test cases is at most 5×1055 \times 10^55×105
  • 1≤wi≤1091 \le w_i \le 10^91≤wi​≤109
  • Each edge connects one left vertex to one right vertex
  • There are no duplicate edges

The input is given in the following format:

ttt LRmw1w2⋯wL+Ru1v1u2v2⋮umvm}×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 tLRmw1​w2​⋯wL+R​u1​v1​u2​v2​⋮um​vm​​⎭⎬⎫​×t

For each edge, 1≤ui≤L1 \le u_i \le L1≤ui​≤L and L+1≤vi≤L+RL+1 \le v_i \le L+RL+1≤vi​≤L+R.

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

Then output kkk distinct integers x1,x2,…,xkx_1,x_2,\ldots,x_kx1​,x2​,…,xk​, the vertices you choose.

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

The output format is:

kx1x2⋯xk}×t\left. \begin{array}{l} k \\ x_1 \quad x_2 \quad \cdots \quad x_k \end{array} \right\} \times tkx1​x2​⋯xk​​}×t

If k=0k=0k=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,31,2,31,2,3.

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

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