#include #include #include #include #include using namespace std; // Function to interact with the system // ops: list of lamp IDs to toggle // returns: vector of booleans (0 or 1) indicating adjacency status after each op vector query(const vector& ops) { if (ops.empty()) return {}; cout << ops.size(); for (int x : ops) cout << " " << x; cout << endl; vector res(ops.size()); for (int i = 0; i < ops.size(); ++i) { cin >> res[i]; } return res; } void answer(const vector& p) { cout << "-1"; for (int x : p) cout << " " << x; cout << endl; exit(0); } int n; int main() { int subtask; if (!(cin >> subtask >> n)) return 0; // Step 1: Find 3 Independent Sets A, B, C // We do this by finding MIS sequentially. // Query 1: Try adding all 1..n. // Those that don't cause conflict form I1. // However, to clear the state for next step, we must toggle them back? // Actually, we can just track the state. // Let's assume we start empty. // We'll perform batches to classify nodes. // Batch 1: 1..n. Result gives us I1. // But result r_i depends on current S. // We define I1: nodes where r_i == 0. // We know S ends up with I1 + Garbage. // We need to clear S. The system doesn't auto-clear. // We can clear S by toggling everything in I1 + Garbage. // We know exactly what's in S: all i where we sent "toggle i". // So next batch should start with clearing ops. vector p(n); iota(p.begin(), p.end(), 1); // Batch 1 vector q1 = p; vector res1 = query(q1); vector S_state; // What is currently in S vector I1, R1; for (int i = 0; i < n; ++i) { if (res1[i] == 0) { I1.push_back(p[i]); } else { R1.push_back(p[i]); } S_state.push_back(p[i]); } // Batch 2: Clear S, then process R1 to find I2 vector q2 = S_state; // To clear for (int x : R1) q2.push_back(x); vector res2 = query(q2); // The first S_state.size() results are for clearing. // The rest are for R1. vector I2, R2; for (int i = 0; i < R1.size(); ++i) { int r = res2[S_state.size() + i]; if (r == 0) { I2.push_back(R1[i]); } else { R2.push_back(R1[i]); } } // Current S contains elements from R1 processing. // We need to clear them for the next phases. // Current S contents: I2 + Garbage_from_R1. // Garbage_from_R1 are elements in R1 where r==1. // I2 are elements in R1 where r==0. // Basically, all elements of R1 were toggled ON. S_state = R1; vector I3 = R2; // As derived, remaining set is independent vector sets[3] = {I1, I2, I3}; vector node_set_id(n + 1); for (int x : I1) node_set_id[x] = 0; for (int x : I2) node_set_id[x] = 1; for (int x : I3) node_set_id[x] = 2; // Step 2: Determine degrees between sets // We need to distinguish if a node has 1 or 2 neighbors in a target set. // For each u, d_0 + d_1 + d_2 = 2. // We query each set fully to find if degree >= 1. int degree_ge1[3][n + 1]; // [target_set][u] // We need to clear S_state first. // Optimize: Combine degree queries. // Batch 3: Clear S_state. Add I1. Probe I2, I3. // Batch 4: Clear I1 (it's in S). Add I2. Probe I1, I3. // Batch 5: Clear I2. Add I3. Probe I1, I2. // Actually simpler: // Q_deg1: Clear S. Add I1. Probe All (or just R1). // But probing modifies S. We need to restore S. // Probe u: Add u, Check, Remove u. vector q_deg[3]; // Fill q_deg // We need to manage S state carefully. // Let's just assume we start each major step with clean S. // We have S_state to clear. // Helper to generate probe sequence auto append_probe = [&](vector& q, const vector& targets) { for (int u : targets) { q.push_back(u); q.push_back(u); } }; for (int t = 0; t < 3; ++t) { // Clear previous state for (int x : S_state) q_deg[t].push_back(x); // Add target set for (int x : sets[t]) q_deg[t].push_back(x); S_state = sets[t]; // Probe others vector others; for (int i = 0; i < 3; ++i) if (i != t) { for (int x : sets[i]) others.push_back(x); } append_probe(q_deg[t], others); } // Run degree queries for (int t = 0; t < 3; ++t) { vector res = query(q_deg[t]); // Parse // First part: clearing. Ignore. // Second part: adding set t. Ignore. // Third part: probes. // Clearing ops count: previous S_state.size() // Adding ops count: sets[t].size() int offset = (int)q_deg[t].size() - 2 * (n - (int)sets[t].size()); vector others; for (int i = 0; i < 3; ++i) if (i != t) { for (int x : sets[i]) others.push_back(x); } for (int i = 0; i < others.size(); ++i) { int u = others[i]; int r = res[offset + 2 * i]; degree_ge1[t][u] = r; } for (int x : sets[t]) degree_ge1[t][x] = 0; // No edges within set } // Calculate exact degrees int exact_deg[3][n + 1]; // [target_set][u] for (int u = 1; u <= n; ++u) { int my_set = node_set_id[u]; int d[3] = {0, 0, 0}; int sum_ge1 = 0; for (int t = 0; t < 3; ++t) if (t != my_set) sum_ge1 += degree_ge1[t][u]; for (int t = 0; t < 3; ++t) { if (t == my_set) { exact_deg[t][u] = 0; } else { if (degree_ge1[t][u] == 0) exact_deg[t][u] = 0; else { // if sum_ge1 == 2, then we have 1 edge to each of the 2 sets (since total deg=2) // if sum_ge1 == 1, then we have 2 edges to the one set with ge1 if (sum_ge1 == 2) exact_deg[t][u] = 1; else exact_deg[t][u] = 2; } } } } // Step 3: Bit queries vector neighbor_sum(n + 1, 0); for (int k = 0; k < 17; ++k) { // For each set t, query intersection with M_k // Also need intersection with NOT M_k if degree 2 exists // We will perform 6 batches per bit: // For each target set T: // Query T \cap M_k // Query T \cap !M_k // Probing all other nodes for (int t = 0; t < 3; ++t) { for (int type = 0; type < 2; ++type) { // 0: M_k, 1: !M_k vector q; // Clear S for (int x : S_state) q.push_back(x); // Construct target subset vector target_subset; for (int x : sets[t]) { int bit = (x >> k) & 1; if ((type == 0 && bit == 1) || (type == 1 && bit == 0)) { target_subset.push_back(x); } } for (int x : target_subset) q.push_back(x); S_state = target_subset; // Probe others vector others; for (int i = 0; i < 3; ++i) if (i != t) { for (int x : sets[i]) others.push_back(x); } append_probe(q, others); vector res = query(q); int offset = (int)q.size() - 2 * (int)others.size(); for (int i = 0; i < others.size(); ++i) { int u = others[i]; int r = res[offset + 2 * i]; // Logic to update sum // If degree is 1: we only care about type 0 (M_k). If r=1, neighbor has bit k. // If degree is 2: // We need sum of bits. // S1 = res from M_k probe. S0 = res from !M_k probe. // Sum bits = S1 + (1 - S0). int deg = exact_deg[t][u]; if (deg == 1) { if (type == 0 && r == 1) { neighbor_sum[u] += (1LL << k); } } else if (deg == 2) { if (type == 0) { // M_k if (r == 1) neighbor_sum[u] += (1LL << k); } else { // !M_k if (r == 0) neighbor_sum[u] += (1LL << k); // +1 contribution } } } } } } // Step 4: Reconstruct Ring // Try to find one neighbor of 1 // Since we know sum_neighbors[1], if we pick neighbor v, other is sum - v. // Validate. for (int start_node = 2; start_node <= n; ++start_node) { vector path; path.push_back(1); path.push_back(start_node); vector visited(n + 1, false); visited[1] = true; visited[start_node] = true; bool possible = true; int curr = start_node; int prev = 1; for (int i = 0; i < n - 2; ++i) { long long next_sum = neighbor_sum[curr]; int next = (int)(next_sum - prev); if (next < 1 || next > n || visited[next]) { possible = false; break; } visited[next] = true; path.push_back(next); prev = curr; curr = next; } if (possible) { // Check loop closure long long last_sum = neighbor_sum[curr]; int closure = (int)(last_sum - prev); if (closure == 1) { // Also check consistency for 1 long long one_sum = neighbor_sum[1]; if (one_sum - curr == start_node) { answer(path); } } } } return 0; }