[Solution] Matching Reduction solution codeforces

Table of Contents

Matching Reduction solution codeforces

Matching Reduction solution codeforces – You are given a bipartite graph with 𝑛1n1 vertices in the first part, 𝑛2n2 vertices in the second part, and 𝑚m edges. The maximum matching in this graph is the maximum possible (by size) subset of edges of this graph such that no vertex is incident to more than one chosen edge.

You have to process two types of queries to this graph:

  • 11 — remove the minimum possible number of vertices from this graph so that the size of the maximum matching gets reduced exactly by 11, and print the vertices that you have removed. Then, find any maximum matching in this graph and print the sum of indices of edges belonging to this matching;
  • 22 — query of this type will be asked only after a query of type 11. As the answer to this query, you have to print the edges forming the maximum matching you have chosen in the previous query.

Matching Reduction solution codeforces

Note that you should solve the problem in online mode. It means that you can’t read the whole input at once. You can read each query only after writing the answer for the last query. Use functions fflush in C++ and BufferedWriter.flush in Java languages after each writing in your program.

Input

The first line contains four integers 𝑛1n1𝑛2n2𝑚m and 𝑞q (1𝑛1,𝑛221051≤n1,n2≤2⋅1051𝑚min(𝑛1𝑛2,2105)1≤m≤min(n1⋅n2,2⋅105)1𝑞21051≤q≤2⋅105).

Then 𝑚m lines follow. The 𝑖i-th of them contains two integers 𝑥𝑖xi and 𝑦𝑖yi (1𝑥𝑖𝑛11≤xi≤n11𝑦𝑖𝑛21≤yi≤n2) meaning that the 𝑖i-th edge connects the vertex 𝑥𝑖xi in the first part and the vertex 𝑦𝑖yi in the second part. There are no pairs of vertices that are connected by more than one edge.

Then 𝑞q lines follow. The 𝑖i-th of them contains one integer, 11 or 22, denoting the 𝑖i-th query. Additional constraints on queries:

  • the number of queries of type 11 won’t exceed the size of the maximum matching in the initial graph;
  • the number of queries of type 22 won’t exceed 33;
  • each query of type 22 is preceded by a query of type 11;
  • your solution is allowed to read the 𝑖i-th query only after printing the answer for the (𝑖1)(i−1)-th query and flushing the output.

Matching Reduction solution codeforces

For a query of type 11, print the answer in three lines as follows:

  • the first line should contain the number of vertices you remove;
  • the second line should contain the indices of vertices you remove, as follows: if you remove the vertex 𝑥x from the left part, print 𝑥x; if you remove the vertex 𝑦y from the right part, print 𝑦−y (negative index);
  • the third line should contain the sum of indices of edges in some maximum matching in the resulting graph. The edges are numbered from 11 to 𝑚m.

For a query of type 22, print the answer in two lines as follows:

  • the first line should contain the size of the maximum matching;
  • the second line should contain the indices of the edges belonging to the maximum matching. Note that the sum of these indices should be equal to the number you printed at the end of the previous query of type 11;

After printing the answer to a query, don’t forget to flush the output.

Example
input

Copy
3 4 4 4
2 2
1 3
2 1
3 4
1
2
1
2
output

Copy
1
-4
3
===
2
1 2
===
1
2
2
===
1
2

Matching Reduction solution codeforces

In this problem, you may receive the verdict “Idleness Limit Exceeded” since it is in online mode. If it happens, it means that either the output format is wrong, or you don’t meet some constraint of the problem. You may treat this verdict as “Wrong Answer”.

For your convenience, the output for queries in the example is separated by the line ===Don’t print this line in your program, it is done only to make sure that it’s easy to distinguish between answers for different queries in the statement.

 

For Solution

“Click Here”

Leave a Comment