309705: CF1721F. Matching Reduction
Memory Limit：512 MB
Time Limit：8 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Matching Reduction
题意翻译
给定一个二分图，其中左边有 $n_1$个点，右边有 $n_2$ 个点，共 $m$ 条边，编号为 $1\sim m$。你需要在线地进行如下 $q$ 个操作： - 操作 $1$：删去最少数量的点，使得二分图的最大匹配减少恰好 $1$，并在删除之后，输出当前最大匹配中所有边的编号之和。 - 操作 $2$：输出当前在最大匹配中的所有边的编号。 对于询问的额外限制： 1. 第一种询问只会有至多一开始图的最大匹配次。 2. 第二种询问只会有至多 **3** 次。 3. 每个第二种询问前面都是第一种询问。（第二种询问不会连续出现。） 4. 你的程序只能在输出第 $i$ 个询问的答案并清空输出流后读入第 $i+1$ 个询问。题目描述
You are given a bipartite graph with $ n_1 $ vertices in the first part, $ n_2 $ 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: - $ 1 $ — remove the minimum possible number of vertices from this graph so that the size of the maximum matching gets reduced exactly by $ 1 $ , 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; - $ 2 $ — query of this type will be asked only after a query of type $ 1 $ . As the answer to this query, you have to print the edges forming the maximum matching you have chosen in the previous query. 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.输入输出格式
输入格式
The first line contains four integers $ n_1 $ , $ n_2 $ , $ m $ and $ q $ ( $ 1 \le n_1, n_2 \le 2 \cdot 10^5 $ ; $ 1 \le m \le \min(n_1 \cdot n_2, 2 \cdot 10^5) $ ; $ 1 \le q \le 2 \cdot 10^5 $ ). Then $ m $ lines follow. The $ i $ -th of them contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i \le n_1 $ ; $ 1 \le y_i \le n_2 $ ) meaning that the $ i $ -th edge connects the vertex $ x_i $ in the first part and the vertex $ y_i $ 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, $ 1 $ or $ 2 $ , denoting the $ i $ -th query. Additional constraints on queries: - the number of queries of type $ 1 $ won't exceed the size of the maximum matching in the initial graph; - the number of queries of type $ 2 $ won't exceed $ 3 $ ; - each query of type $ 2 $ is preceded by a query of type $ 1 $ ; - your solution is allowed to read the $ i $ -th query only after printing the answer for the $ (i-1) $ -th query and flushing the output.
输出格式
For a query of type $ 1 $ , 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 $ 1 $ to $ m $ . For a query of type $ 2 $ , 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 $ 1 $ ; After printing the answer to a query, don't forget to flush the output.
输入输出样例
输入样例 #1
3 4 4 4
2 2
1 3
2 1
3 4
1
2
1
2输出样例 #1
1
-4
3
===
2
1 2
===
1
2
2
===
1
2说明
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.Input
题意翻译
给定一个二分图，其中左边有 $n_1$个点，右边有 $n_2$ 个点，共 $m$ 条边，编号为 $1\sim m$。你需要在线地进行如下 $q$ 个操作： - 操作 $1$：删去最少数量的点，使得二分图的最大匹配减少恰好 $1$，并在删除之后，输出当前最大匹配中所有边的编号之和。 - 操作 $2$：输出当前在最大匹配中的所有边的编号。 对于询问的额外限制： 1. 第一种询问只会有至多一开始图的最大匹配次。 2. 第二种询问只会有至多 **3** 次。 3. 每个第二种询问前面都是第一种询问。（第二种询问不会连续出现。） 4. 你的程序只能在输出第 $i$ 个询问的答案并清空输出流后读入第 $i+1$ 个询问。Output
**题意翻译**
给定一个二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，共有 $m$ 条边，边的编号为 $1$ 到 $m$。需要在线地处理 $q$ 个操作：
- 操作 $1$：删除最少的点数，使得二分图的最大匹配数恰好减少 $1$，在删除后，输出当前最大匹配中所有边的编号之和。
- 操作 $2$：输出当前最大匹配中所有边的编号。
对于操作的额外限制：
1. 第一种操作最多只有初始图的最大匹配次数。
2. 第二种操作最多只有 **3** 次。
3. 每个第二种操作前面都是第一种操作。（第二种操作不会连续出现。）
4. 程序只能在输出第 $i$ 个操作的答案并清空输出流后，才能读入第 $i+1$ 个操作。
**题目描述**
给定一个二分图，第一部分有 $n_1$ 个顶点，第二部分有 $n_2$ 个顶点，共有 $m$ 条边。图的最大匹配是图边的一个最大可能子集，使得没有顶点与多于一个选择的边相关联。
你需要处理两种类型的查询：
- $1$ — 从图中删除尽可能少的顶点，使得最大匹配的大小正好减少 $1$，然后输出你删除的顶点。接着，在剩余的图中找到任何最大匹配，并输出属于这个匹配的边的编号之和。
- $2$ — 这种类型的查询将在类型 $1$ 的查询之后提出。作为这种查询的答案，你需要输出你在前一个查询中选择的最大匹配的边。
注意，你需要在线模式下解决问题。这意味着你不能一次读取所有输入。你只能在写出上一个查询的答案后读取每个查询。在你的程序中，每次写入后使用 C++ 语言的 fflush 函数和 Java 语言的 BufferedWriter.flush 方法刷新输出。
**输入输出格式**
**输入格式**
第一行包含四个整数 $n_1$、$n_2$、$m$ 和 $q$（$1 \le n_1, n_2 \le 2 \cdot 10^5$；$1 \le m \le \min(n_1 \cdot n_2, 2 \cdot 10^5)$；$1 \le q \le 2 \cdot 10^5$）。
接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n_1$；$1 \le y_i \le n_2$），表示第 $i$ 条边连接第一部分的顶点 $x_i$ 和第二部分的顶点 $y_i$。不会有超过一条边连接一对顶点。
接下来 $q$ 行，每行包含一个整数，$1$ 或 $2$，表示第 $i$ 个查询。查询的额外限制如下：
- 类型 $1$ 的查询次数不会超过初始图的最大匹配大小；
- 类型 $2$ 的查询次数不会超过 $3$；
- 每个类型 $2$ 的查询前面都是一个类型 $1$ 的查询；
- 你的解决方案只能在打印出第 $i-1$ 个查询的答案并刷新输出后读取第 $i$ 个查询。
**输出格式**
对于类型 $1$ 的查询，按以下格式打印答案：
- 第一行应包含你删除的顶点数；
- 第二行应包含你删除的顶点索引，格式如下：如果你删除了左部分的顶点 $x$，打印 $x$；如果你删除了右部分的顶点 $y$，打印 $-y$（负索引）；
- 第三行应包含结果图中某个最大匹配的边编号之和。边的编号从 $1$ 到 $m$。
对于类型 $2$ 的查询，按以下格式打印答案：
- 第一行应包含最大匹配的大小；
- 第二行应包含属于最大匹配的边的编号。注意，这些编号之和应等于你在上一个类型 $1$ 的查询结束时打印的数字。
在打印出一个查询的答案后，别忘了刷新输出。
**输入输出样例**
**输入样例 #1**
```
3 4 4 4
2 2
1 3
2 1
3 4
1
2
1
2
```
**输出样例 #1**
```
1
-4
3
===
2
1 2
===
1
2
2
===
1
2
```
**说明**
在这个问题中，由于是在线模式，你可能会收到“Idleness Limit Exceeded”的判定结果。如果发生这种情况，这意味着输出格式错误，或者你没有满足问题的某些约束。你可以将这种判定结果视为“Wrong Answer”。
为了方便起见，示例**题意翻译** 给定一个二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，共有 $m$ 条边，边的编号为 $1$ 到 $m$。需要在线地处理 $q$ 个操作： - 操作 $1$：删除最少的点数，使得二分图的最大匹配数恰好减少 $1$，在删除后，输出当前最大匹配中所有边的编号之和。 - 操作 $2$：输出当前最大匹配中所有边的编号。 对于操作的额外限制： 1. 第一种操作最多只有初始图的最大匹配次数。 2. 第二种操作最多只有 **3** 次。 3. 每个第二种操作前面都是第一种操作。（第二种操作不会连续出现。） 4. 程序只能在输出第 $i$ 个操作的答案并清空输出流后，才能读入第 $i+1$ 个操作。 **题目描述** 给定一个二分图，第一部分有 $n_1$ 个顶点，第二部分有 $n_2$ 个顶点，共有 $m$ 条边。图的最大匹配是图边的一个最大可能子集，使得没有顶点与多于一个选择的边相关联。 你需要处理两种类型的查询： - $1$ — 从图中删除尽可能少的顶点，使得最大匹配的大小正好减少 $1$，然后输出你删除的顶点。接着，在剩余的图中找到任何最大匹配，并输出属于这个匹配的边的编号之和。 - $2$ — 这种类型的查询将在类型 $1$ 的查询之后提出。作为这种查询的答案，你需要输出你在前一个查询中选择的最大匹配的边。 注意，你需要在线模式下解决问题。这意味着你不能一次读取所有输入。你只能在写出上一个查询的答案后读取每个查询。在你的程序中，每次写入后使用 C++ 语言的 fflush 函数和 Java 语言的 BufferedWriter.flush 方法刷新输出。 **输入输出格式** **输入格式** 第一行包含四个整数 $n_1$、$n_2$、$m$ 和 $q$（$1 \le n_1, n_2 \le 2 \cdot 10^5$；$1 \le m \le \min(n_1 \cdot n_2, 2 \cdot 10^5)$；$1 \le q \le 2 \cdot 10^5$）。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n_1$；$1 \le y_i \le n_2$），表示第 $i$ 条边连接第一部分的顶点 $x_i$ 和第二部分的顶点 $y_i$。不会有超过一条边连接一对顶点。 接下来 $q$ 行，每行包含一个整数，$1$ 或 $2$，表示第 $i$ 个查询。查询的额外限制如下： - 类型 $1$ 的查询次数不会超过初始图的最大匹配大小； - 类型 $2$ 的查询次数不会超过 $3$； - 每个类型 $2$ 的查询前面都是一个类型 $1$ 的查询； - 你的解决方案只能在打印出第 $i-1$ 个查询的答案并刷新输出后读取第 $i$ 个查询。 **输出格式** 对于类型 $1$ 的查询，按以下格式打印答案： - 第一行应包含你删除的顶点数； - 第二行应包含你删除的顶点索引，格式如下：如果你删除了左部分的顶点 $x$，打印 $x$；如果你删除了右部分的顶点 $y$，打印 $-y$（负索引）； - 第三行应包含结果图中某个最大匹配的边编号之和。边的编号从 $1$ 到 $m$。 对于类型 $2$ 的查询，按以下格式打印答案： - 第一行应包含最大匹配的大小； - 第二行应包含属于最大匹配的边的编号。注意，这些编号之和应等于你在上一个类型 $1$ 的查询结束时打印的数字。 在打印出一个查询的答案后，别忘了刷新输出。 **输入输出样例** **输入样例 #1** ``` 3 4 4 4 2 2 1 3 2 1 3 4 1 2 1 2 ``` **输出样例 #1** ``` 1 -4 3 === 2 1 2 === 1 2 2 === 1 2 ``` **说明** 在这个问题中，由于是在线模式，你可能会收到“Idleness Limit Exceeded”的判定结果。如果发生这种情况，这意味着输出格式错误，或者你没有满足问题的某些约束。你可以将这种判定结果视为“Wrong Answer”。 为了方便起见，示例
给定一个二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，共有 $m$ 条边，边的编号为 $1$ 到 $m$。需要在线地处理 $q$ 个操作：
- 操作 $1$：删除最少的点数，使得二分图的最大匹配数恰好减少 $1$，在删除后，输出当前最大匹配中所有边的编号之和。
- 操作 $2$：输出当前最大匹配中所有边的编号。
对于操作的额外限制：
1. 第一种操作最多只有初始图的最大匹配次数。
2. 第二种操作最多只有 **3** 次。
3. 每个第二种操作前面都是第一种操作。（第二种操作不会连续出现。）
4. 程序只能在输出第 $i$ 个操作的答案并清空输出流后，才能读入第 $i+1$ 个操作。
**题目描述**
给定一个二分图，第一部分有 $n_1$ 个顶点，第二部分有 $n_2$ 个顶点，共有 $m$ 条边。图的最大匹配是图边的一个最大可能子集，使得没有顶点与多于一个选择的边相关联。
你需要处理两种类型的查询：
- $1$ — 从图中删除尽可能少的顶点，使得最大匹配的大小正好减少 $1$，然后输出你删除的顶点。接着，在剩余的图中找到任何最大匹配，并输出属于这个匹配的边的编号之和。
- $2$ — 这种类型的查询将在类型 $1$ 的查询之后提出。作为这种查询的答案，你需要输出你在前一个查询中选择的最大匹配的边。
注意，你需要在线模式下解决问题。这意味着你不能一次读取所有输入。你只能在写出上一个查询的答案后读取每个查询。在你的程序中，每次写入后使用 C++ 语言的 fflush 函数和 Java 语言的 BufferedWriter.flush 方法刷新输出。
**输入输出格式**
**输入格式**
第一行包含四个整数 $n_1$、$n_2$、$m$ 和 $q$（$1 \le n_1, n_2 \le 2 \cdot 10^5$；$1 \le m \le \min(n_1 \cdot n_2, 2 \cdot 10^5)$；$1 \le q \le 2 \cdot 10^5$）。
接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n_1$；$1 \le y_i \le n_2$），表示第 $i$ 条边连接第一部分的顶点 $x_i$ 和第二部分的顶点 $y_i$。不会有超过一条边连接一对顶点。
接下来 $q$ 行，每行包含一个整数，$1$ 或 $2$，表示第 $i$ 个查询。查询的额外限制如下：
- 类型 $1$ 的查询次数不会超过初始图的最大匹配大小；
- 类型 $2$ 的查询次数不会超过 $3$；
- 每个类型 $2$ 的查询前面都是一个类型 $1$ 的查询；
- 你的解决方案只能在打印出第 $i-1$ 个查询的答案并刷新输出后读取第 $i$ 个查询。
**输出格式**
对于类型 $1$ 的查询，按以下格式打印答案：
- 第一行应包含你删除的顶点数；
- 第二行应包含你删除的顶点索引，格式如下：如果你删除了左部分的顶点 $x$，打印 $x$；如果你删除了右部分的顶点 $y$，打印 $-y$（负索引）；
- 第三行应包含结果图中某个最大匹配的边编号之和。边的编号从 $1$ 到 $m$。
对于类型 $2$ 的查询，按以下格式打印答案：
- 第一行应包含最大匹配的大小；
- 第二行应包含属于最大匹配的边的编号。注意，这些编号之和应等于你在上一个类型 $1$ 的查询结束时打印的数字。
在打印出一个查询的答案后，别忘了刷新输出。
**输入输出样例**
**输入样例 #1**
```
3 4 4 4
2 2
1 3
2 1
3 4
1
2
1
2
```
**输出样例 #1**
```
1
-4
3
===
2
1 2
===
1
2
2
===
1
2
```
**说明**
在这个问题中，由于是在线模式，你可能会收到“Idleness Limit Exceeded”的判定结果。如果发生这种情况，这意味着输出格式错误，或者你没有满足问题的某些约束。你可以将这种判定结果视为“Wrong Answer”。
为了方便起见，示例**题意翻译** 给定一个二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，共有 $m$ 条边，边的编号为 $1$ 到 $m$。需要在线地处理 $q$ 个操作： - 操作 $1$：删除最少的点数，使得二分图的最大匹配数恰好减少 $1$，在删除后，输出当前最大匹配中所有边的编号之和。 - 操作 $2$：输出当前最大匹配中所有边的编号。 对于操作的额外限制： 1. 第一种操作最多只有初始图的最大匹配次数。 2. 第二种操作最多只有 **3** 次。 3. 每个第二种操作前面都是第一种操作。（第二种操作不会连续出现。） 4. 程序只能在输出第 $i$ 个操作的答案并清空输出流后，才能读入第 $i+1$ 个操作。 **题目描述** 给定一个二分图，第一部分有 $n_1$ 个顶点，第二部分有 $n_2$ 个顶点，共有 $m$ 条边。图的最大匹配是图边的一个最大可能子集，使得没有顶点与多于一个选择的边相关联。 你需要处理两种类型的查询： - $1$ — 从图中删除尽可能少的顶点，使得最大匹配的大小正好减少 $1$，然后输出你删除的顶点。接着，在剩余的图中找到任何最大匹配，并输出属于这个匹配的边的编号之和。 - $2$ — 这种类型的查询将在类型 $1$ 的查询之后提出。作为这种查询的答案，你需要输出你在前一个查询中选择的最大匹配的边。 注意，你需要在线模式下解决问题。这意味着你不能一次读取所有输入。你只能在写出上一个查询的答案后读取每个查询。在你的程序中，每次写入后使用 C++ 语言的 fflush 函数和 Java 语言的 BufferedWriter.flush 方法刷新输出。 **输入输出格式** **输入格式** 第一行包含四个整数 $n_1$、$n_2$、$m$ 和 $q$（$1 \le n_1, n_2 \le 2 \cdot 10^5$；$1 \le m \le \min(n_1 \cdot n_2, 2 \cdot 10^5)$；$1 \le q \le 2 \cdot 10^5$）。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n_1$；$1 \le y_i \le n_2$），表示第 $i$ 条边连接第一部分的顶点 $x_i$ 和第二部分的顶点 $y_i$。不会有超过一条边连接一对顶点。 接下来 $q$ 行，每行包含一个整数，$1$ 或 $2$，表示第 $i$ 个查询。查询的额外限制如下： - 类型 $1$ 的查询次数不会超过初始图的最大匹配大小； - 类型 $2$ 的查询次数不会超过 $3$； - 每个类型 $2$ 的查询前面都是一个类型 $1$ 的查询； - 你的解决方案只能在打印出第 $i-1$ 个查询的答案并刷新输出后读取第 $i$ 个查询。 **输出格式** 对于类型 $1$ 的查询，按以下格式打印答案： - 第一行应包含你删除的顶点数； - 第二行应包含你删除的顶点索引，格式如下：如果你删除了左部分的顶点 $x$，打印 $x$；如果你删除了右部分的顶点 $y$，打印 $-y$（负索引）； - 第三行应包含结果图中某个最大匹配的边编号之和。边的编号从 $1$ 到 $m$。 对于类型 $2$ 的查询，按以下格式打印答案： - 第一行应包含最大匹配的大小； - 第二行应包含属于最大匹配的边的编号。注意，这些编号之和应等于你在上一个类型 $1$ 的查询结束时打印的数字。 在打印出一个查询的答案后，别忘了刷新输出。 **输入输出样例** **输入样例 #1** ``` 3 4 4 4 2 2 1 3 2 1 3 4 1 2 1 2 ``` **输出样例 #1** ``` 1 -4 3 === 2 1 2 === 1 2 2 === 1 2 ``` **说明** 在这个问题中，由于是在线模式，你可能会收到“Idleness Limit Exceeded”的判定结果。如果发生这种情况，这意味着输出格式错误，或者你没有满足问题的某些约束。你可以将这种判定结果视为“Wrong Answer”。 为了方便起见，示例