You are given a graph with 3 ⋅ n vertices and m edges. You are to find a matching of n…
- User
You are given a graph with 3 ⋅ n vertices and m edges. You are to find a matching of n edges, or an independent set of n vertices.
A set of edges is called a matching if no two edges share an endpoint.
A set of vertices is called an independent set if no two vertices are connected with an edge. Input
The first line contains a single integer T ≥ 1 — the number of graphs you need to process. The description of T graphs follows.
The first line of description of a single graph contains two integers n and m, where 3 ⋅ n is the number of vertices, and m is the number of edges in the graph (1 ≤ n ≤ 10^{5}, 0 ≤ m ≤ 5 ⋅ 10^{5}).
Each of the next m lines contains two integers v_i and u_i (1 ≤ v_i, u_i ≤ 3 ⋅ n), meaning that there is an edge between vertices v_i and u_i.
It is guaranteed that there are no self-loops and no multiple edges in the graph.
It is guaranteed that the sum of all n over all graphs in a single test does not exceed 10^{5}, and the sum of all m over all graphs in a single test does not exceed 5 ⋅ 10^{5}.
Output
Print your answer for each of the T graphs. Output your answer for a single graph in the following format.
If you found a matching of size n, on the first line print "Matching" (without quotes), and on the second line print n integers — the indices of the edges in the matching. The edges are numbered from 1 to m in the input order.
If you found an independent set of size n, on the first line print "IndSet" (without quotes), and on the second line print n integers — the indices of the vertices in the independent set.
If there is no matching and no independent set of the specified size, print "Impossible" (without quotes).
You can print edges and vertices in any order.
If there are several solutions, print any. In particular, if there are both a matching of size n, and an independent set of size n, then you should print exactly one of such matchings or exactly one of such independent sets.
Example
Input
4 1 2 1 3 1 2 1 2 1 3 1 2 2 5 1 2 3 1 1 4 5 1 1 6 2 15 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
Output
Matching 2 IndSet 1 IndSet 2 4 Matching 1 15
Note
The first two graphs are same, and there are both a matching of size 1 and an independent set of size 1. Any of these matchings and independent sets is a correct answer.
The third graph does not have a matching of size 2, however, there is an independent set of size 2. Moreover, there is an independent set of size 5: 2 3 4 5 6. However such answer is not correct, because you are asked to find an independent set (or matching) of size exactly n.
The fourth graph does not have an independent set of size 2, but there is a matching of size 2.
Assistant
We need to understand the problem: For each graph with 3n vertices and m edges, we must output either a matching of size n (i.e., n edges that are vertex-disjoint) or an independent set of size n (i.e., n vertices with no edges between any two). The claim is that in any such graph, at least one of these exists. Indeed, this is a classic combinatorial result: In any graph on 3n vertices, either there is a matching of size n or an independent set of size n. Actually, is that always true? Let's think: Consider the complement. If there is no independent set of size n, then the graph's complement has no matching of size n? Hmm maybe by Turán type or by applying a known theorem: The Erdős–Gallai? Actually, there's a well-known problem from Codeforces: "Matching vs Independent Set" (CF 1198C? Actually the problem is exactly "Matching vs Independent Set" from Codeforces Round #1198 (Div. 2) problem C). The solution is to greedily find a maximal matching, and then if its size is at least n, we are done; else the set of vertices not incident to the matching forms an independent set of size at least n. Because total vertices = 3n. If maximal matching has size k < n, then the number of vertices covered by the matching is 2k. The remaining vertices are 3n - 2k >= 3n - 2(n-1) = n+2, actually if k <= n-1, then remaining >= 3n - 2(n-1) = n+2. But are those vertices necessarily independent? In a maximal matching, no edge exists between any two unmatched vertices because if there were an edge between them, we could have added it to the matching, contradicting maximality. So the set of unmatched vertices is independent. So we have an independent set of size at least n+2? Actually careful: The maximal matching property ensures that there is no edge between any two unmatched vertices (since otherwise the matching isn't maximal). However, it's possible that some unmatched vertex has an edge to a matched vertex; that's fine. So indeed, the set of all unmatched vertices is an independent set. Its size is 3n - 2k. If k < n, then 3n - 2k > 3n - 2(n-1) = n+2 > n, so it is at least n+? But we need exactly n vertices; we can just take any n of them. So the greedy algorithm works.
But the problem statement also includes the possibility of both solutions; we can output either. And they guarantee that T graphs with sum of n ≤ 1e5, sum of m ≤ 5e5.
Thus algorithm: For each graph, read n,m. Read edges. We'll perform a greedy maximal matching: We iterate edges in order, and maintain a boolean array visited[3n+1] to indicate if a vertex is already matched. For each edge (u,v) (index i), if neither u nor v is matched, then we add this edge to the matching (record its index), mark both vertices as matched. Continue until we either have collected n edges (then we can stop and output Matching with those edges) or we have processed all edges. After processing all edges, we will have some matching size k (maybe less than n). Then we can output Independent Set: collect all vertices that are unmatched (i.e., not visited), take the first n of them, output indices.
We need to be careful: The visited array size up to 3n, but sum of n across tests ≤ 1e5, so total vertices ≤ 3*1e5 = 300k, which is fine. Also total edges ≤ 5e5, fine.
But wait: Is it guaranteed that the unmatched set is independent? Let's double-check: For maximal matching, by definition it's a matching that cannot be extended by adding any edge. However, our greedy algorithm constructs a maximal matching? The algorithm described (iterate edges, take if both endpoints free) yields a maximal matching? Actually, it yields a maximal matching in the sense that after processing all edges, there is no edge left with both endpoints free? Not necessarily. The standard greedy algorithm (in arbitrary order) does not guarantee maximal matching? Let's think: Suppose we process edges in some order; we take an edge if both endpoints are free. After we finish, could there be an edge with both endpoints free? That would mean that when we processed that edge, both endpoints were free, so we would have taken it. Since we processed it, we would have taken it. Thus after processing all edges, there is no edge left with both endpoints free. Therefore the matching is maximal. So indeed the greedy algorithm yields a maximal matching (not necessarily maximum, but maximal). So unmatched vertices form an independent set.
Thus the algorithm works.
Now consider constraints: The input may have T graphs. For each graph, we need to output either "Matching" and list of n edge indices, or "IndSet" and list of n vertex indices.
Potential pitfalls: The greedy algorithm might stop early when we have found n edges (size matching). But we need to be sure that if we stop early, the unmatched vertices independent set is not needed. That's fine. But we must ensure that if we stop early, the matching we have is valid: no vertices repeated. Since we only add edges when both endpoints are free, it's fine.
Edge indices: edges are numbered from 1 to m in input order. We need to output the indices of the edges we selected.
If we stop early after we have n edges, we haven't processed the remaining edges, but that's okay.
Now, what about the case where we might find a matching of size n but we also could output independent set. Either is acceptable.
Also, note that the problem says: "If there is no matching and no independent set of the specified size, print "Impossible"." But by the combinatorial argument, at least one exists; so we will never output "Impossible". But they include it for completeness? Possibly some test cases might violate the property? But given the guarantee that the graph has 3n vertices, at least one of these exists. So we can ignore "Impossible".
Implementation details: Since T up to maybe 100k? Sum n ≤ 1e5, but T could be large, but we need to handle multiple test cases efficiently.
We'll read T.
For each test case:
-
Read n, m.
-
Create arrays: visited = vector or vector of size 3*n+1, initialized to 0. (We'll use vector with 0/1 to avoid bitset overhead? But bool is fine.)
-
vector matchingEdges; // store indices.
-
For i from 1 to m: read u, v. if visited[u]==0 and visited[v]==0: matchingEdges.push_back(i); visited[u]=1; visited[v]=1; if matchingEdges.size() == n: break; // we can stop reading? But we need to read remaining edges? Actually we still need to consume the input lines. So we cannot break the loop early if there are more edges to read. Since we break out of reading loop, we would skip the remaining input lines for this graph. That would cause the next test case to be read incorrectly. So we must read all m edges regardless. So we cannot break early from the loop; but we can break early after we have already collected n edges, but we still need to read the remaining edges and ignore them. So we can continue reading but skip processing (i.e., just read and discard, not check). Alternatively, we could read all edges first and store them? But m can be up to 5e5 total, it's okay to store edges? But memory wise, we could also read edge by edge and not store all. However we might need to output edge indices; we only need the indices we select. So we can process on the fly: if we have already collected n edges, we can just continue reading without any operation (just consume input). That's efficient. So we need to finish reading m lines. So we do a for loop over i=1..m, read u,v; if matchingEdges.size() < n and !visited[u] and !visited[v] then take it.
-
After reading all edges, we have either matchingEdges.size() >= n or not.
-
If matchingEdges.size() >= n: Output "Matching", then output the first n indices (since we may have more than n? Actually we stop adding once we have n edges, so exactly n). If we stopped early after reaching n, we never add more, so size is exactly n. However, if we never break adding, we could have more than n? Our condition is only when size < n we add. So we add at most n. So it's either exactly n if we reach n, else less than n.
-
So if matchingEdges.size() == n: output them.
-
Else: we output independent set: collect all vertices i from 1 to 3n where visited[i]==0. That should be 3n - 2*k, where k = matchingEdges.size(). Since k < n, we have at least n+2 vertices (if k = n-1, leftover = 3n - 2(n-1) = n+2). So we can take the first n of those vertices. Output "IndSet" and those n vertices.
Time complexity: O(m) per test case, overall O(total m). Memory: O(n) per test case (visited array). Works.
One nuance: When we collect independent set, we need to output vertex indices, not edge indices.
Now, confirm with sample input.
Sample input: 4 1 2 1 3 1 2 1 2 1 3 1 2 2 5 1 2 3 1 1 4 5 1 1 6 2 15 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
Let's simulate quickly.
First test: n=1,m=2. Edges: (1,3), (1,2). Process: i=1: u=1,v=3: both free -> take edge 1, visited 1,3. matchingEdges=[1]; size=1 = n, but still need to read next edge? Yes, read i=2: (1,2) but we still read it; we have size==n so we don't add. After loop, matchingEdges size =1 => output Matching with index 1. But sample output says Matching 2? Hmm sample output for first graph is "Matching" and then "2". Actually output: for the first test, they output "Matching" then "2". That corresponds to edge index 2. They used a different matching? Because they said any solution is correct. In our algorithm we got edge 1. But it's fine, they accept any. But note they processed second test? Wait they have 4 graphs in input. The output for first two graphs are "Matching" "2" and "IndSet" "1"? Actually output lines:
Matching 2 IndSet 1 IndSet 2 4 Matching 1 15
So for first graph, they output matching with edge 2. For second graph, independent set with vertex 1. For third, independent set with vertices 2 and 4. For fourth, matching with edges 1 and 15.
Our algorithm would produce matching for first graph maybe edge 1 (if the order is (1,3) then (1,2)). So it's valid.
Second test: The input: after first test, we have next lines: "1 2" "1 3" "1 2"? Actually input format: The first graph: n=1,m=2, edges: (1,3) and (1,2). Then second graph: n=1,m=2, edges: (1,2) and (1,3)? Wait, need to parse:
The sample input as given:
4 1 2 1 3 1 2 1 2 1 3 1 2 2 5 1 2 3 1 1 4 5 1 1 6 2 15 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
Let's separate:
Test1: n=1 m=2 Edge1: 1 3 Edge2: 1 2
Test2: n=1 m=2? Actually after test1 edges, the next line should be "1 2"? But careful: The input after test1 edges is the next line: "1 2" (maybe that's n=1, m=2 for test2). So test2: n=1 m=2. Edge1: 1 3? Actually after "1 2" line (which is the n,m of test2), next line is "1 2"? Wait line by line:
Line1: 4 Line2: 1 2 -> test1 n=1,m=2 Line3: 1 3 -> test1 edge1 Line4: 1 2 -> test1 edge2 Line5: 1 2 -> test2 n=1,m=2? Actually after test1 edges (2 edges), the next line is "1 2". That would be test2 header: n=1,m=2. Line6: 1 3 -> test2 edge1 Line7: 1 2 -> test2 edge2? But then that would be only one edge? Actually test2 should have m=2, so edges: line6 and line7. So test2: edges: (1,3) and (1,2). Line8: 2 5 -> test3 header: n=2,m=5 Line9: 1 2 -> test3 edge1 Line10: 3 1 -> test3 edge2 Line11: 1 4 -> test3 edge3 Line12: 5 1 -> test3 edge4 Line13: 1 6 -> test3 edge5 Line14: 2 15 -> test4 header: n=2,m=15 Then edges 1..15.
So our algorithm for test2: n=1,m=2; edges: (1,3), (1,2). Process: i=1: (1,3) both free -> take edge1, visited 1,3; matching size=1 = n; read edge2 (1,2) but skip. So we output Matching with edge 1. But sample output for test2 is "IndSet" and "1". That's also valid because independent set of size 1 (vertex 1 is unmatched? Actually after our matching, vertex 1 and 3 are matched, so unmatched vertices are {2}. That's independent set. So they output IndSet with vertex 1? That would be vertex 1 which is matched, but vertex 1 is not independent (it's matched, but independence set can include matched vertices? Wait independent set requires no edges between any two vertices; but it's allowed to include vertices that are incident to edges in the graph, as long as no edge connects two of them. However, if vertex 1 is matched, it still can be in an independent set as long as none of the other vertices in the set are adjacent to it. But if we pick vertex 1 and it has edges to others, but those others are not in the set, it's fine. But can vertex 1 be part of an independent set? Yes, if the set only contains vertex 1, it's trivially independent because there are no pairs. So {1} is an independent set. So indeed, there are multiple possible independent sets. So our algorithm's output for test2 would be matching; both are acceptable. So we can output either. The sample shows that they output IndSet for test2, but it's fine to output Matching. So no problem.
Implementation-wise, we need to be careful that the algorithm yields a correct independent set when needed. The unmatched vertices set is independent; but if we output matching early we don't need independent set. So it's fine.
Now, we must verify that if we cannot get n edges in the greedy, we still have at least n unmatched vertices. As argued: Since matching size k < n, leftover = 3n - 2k >= 3n - 2(n-1) = n+2 >= n. So it's safe.
But is it possible that leftover < n? That would require 3n - 2k < n => 2n < 2k => k > n, which contradicts k < n. So indeed leftover >= n.
One nuance: The greedy algorithm yields a maximal matching, so unmatched vertices form an independent set. But we must ensure that the number of unmatched vertices is indeed at least n. If k is strictly less than n, then 3n - 2k >= 3n - 2(n-1) = n+2. So yes. But what if k = n? Then we output matching. So all good.
Thus algorithm is correct.
Now we need to implement.
Edge case: n may be 1e5 per graph? But total sum of n across tests ≤ 1e5, so it's fine.
Memory: visited array size 3n+1; for each test case, we need to allocate. We can use vector visited(3n+1,0). But because sum of 3n across tests is up to 300k, we could allocate fresh each test.
Alternatively, we can reuse a global visited array if we clear only used positions; but simpler to allocate per test.
Input reading: Use fast IO (e.g., scanf, or cin with sync off).
Also note that we need to output indices of edges from 1..m. We can store matchingEdges vector of int.
Now, let's double-check the greedy algorithm: The order of edges is given by input. The algorithm picks edges if both endpoints free. That yields a maximal matching regardless of order? Yes, as argued: after processing all edges, for any edge, at least one endpoint is matched because when we encountered it, if both were free we would have taken it. So indeed it's maximal.
Potential issue: Could there be a scenario where the greedy picks edges in a way that results in a matching of size less than n but the unmatched vertices set is not independent because of edges between an unmatched vertex and another unmatched vertex that we didn't see? Wait, the greedy processes all edges; if after processing all edges, there remains an edge with both endpoints free, that would mean when that edge was processed, both endpoints were free and we didn't take it, but that only happens if we didn't process it? We process all edges. So if both endpoints free when we process the edge, we take it (since condition checks). However, what about the scenario where after we take some edges, some vertices become matched. But an edge that connects two vertices that become unmatched because they were not matched earlier might be processed later and both endpoints might still be free at that moment, so we would take it. So at the end, there cannot be an edge with both endpoints free. So unmatched vertices set is independent.
Thus fine.
Now we just need to implement for T test cases.
Let's code.
Pseudo:
#include <bits/stdc++.h> using namespace std;
int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int n, m; cin >> n >> m; int totV = 3 * n; vector used(totV + 1, false); vector matchingEdges; matchingEdges.reserve(n); for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; if (matchingEdges.size() < n && !used[u] && !used[v]) { matchingEdges.push_back(i); used[u] = used[v] = true; } } if (matchingEdges.size() == n) { cout << "Matching\n"; for (int idx : matchingEdges) cout << idx << " "; cout << "\n"; } else { vector indSet; for (int i = 1; i <= totV; ++i) { if (!used[i]) indSet.push_back(i); if (indSet.size() == n) break; } cout << "IndSet\n"; for (int v : indSet) cout << v << " "; cout << "\n"; } } return 0; }
That should work.
Double-check sample: For test4: n=2,m=15; the edges are complete graph on 6 vertices? Actually 2*15? Wait test4: n=2, so vertices 6. m=15, which is the complete graph on 6 vertices (since K6 has 15 edges). So greedy will try to pick edges. Let's simulate: start with no vertices used. Process edges in order: 1: (1,2) both free -> take edge1, use 1,2. matchingEdges size=1 (<2). Continue: edge2: (1,3) but 1 used so skip. edge3: (1,4) 1 used skip. edge4: (1,5) skip. edge5: (1,6) skip. edge6: (2,3) 2 used skip. edge7: (2,4) skip. edge8: (2,5) skip. edge9: (2,6) skip. edge10: (3,4) both free -> take edge10, use 3,4. matchingEdges size=2, reaches n. Now continue reading remaining edges (11-15) but not adding. After loop, we output Matching with edges 1 and 10. But sample output for test4 shows "Matching" "1 15". They took edges 1 and 15. That's fine; our output is also valid. So correct.
Now we need to ensure that visited array is of size totV+1 (index from 1). That's fine.
Now we need to consider the possibility that m can be 0. Then greedy will produce no edges, so matchingEdges.size()=0 < n, then we output independent set: we need n vertices from the 3n vertices, all of which are unmatched (since no edges). So we can output any n vertices, e.g., 1..n. But are they independent? Yes, since there are no edges. So fine.
Thus solution is complete.
Now we just need to produce final answer as explanation and code.
But we should also provide reasoning why it's always possible.
Thus final output: Explanation of algorithm and code.
Let's produce final answer. ```cpp
#include <bits/stdc++.h> using namespace std;
int main() { ios_base::sync_with_stdio(false); cin.tie(0);
int T; cin >> T; while (T--) { int n, m; cin >> n >> m; const int V = 3 * n; // total vertices vector<char> used(V + 1, 0); // 1 if vertex is already in the matching vector<int> matching; // indices of chosen edges matching.reserve(n); for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; // take the edge only if we still need edges and both ends are free if (matching.size() < n && !used[u] && !used[v]) { matching.push_back(i); used[u] = used[v] = 1; } } if (matching.size() == n) { cout << "Matching\n"; for (int idx : matching) cout << idx << " "; cout << "\n"; } else { // collect an independent set from the vertices not covered by the matching vector<int> indSet; for (int i = 1; i <= V && indSet.size() < n; ++i) { if (!used[i]) indSet.push_back(i); } cout << "IndSet\n"; for (int v : indSet) cout << v << " "; cout << "\n"; } } return 0;}
-