#include using namespace std; static int N; static inline int readInt() { int c = getchar_unlocked(); while (c != '-' && (c < '0' || c > '9')) { c = getchar_unlocked(); if (c == EOF) return 0; } int sgn = 1; if (c == '-') { sgn = -1; c = getchar_unlocked(); } int x = 0; while (c >= '0' && c <= '9') { x = x*10+(c-'0'); c = getchar_unlocked(); } return x * sgn; } static char wbuf[1 << 23]; static int wpos = 0; static void wflush() { if (wpos > 0) fwrite(wbuf, 1, wpos, stdout); wpos = 0; fflush(stdout); } static void wchar(char c) { if (wpos >= (1<<23)-2) wflush(); wbuf[wpos++] = c; } static void wint(long long x) { if (x < 0) { wchar('-'); x = -x; } if (x == 0) { wchar('0'); return; } char buf[20]; int len = 0; while (x > 0) { buf[len++] = '0'+(int)(x%10); x /= 10; } for (int i = len-1; i >= 0; i--) wchar(buf[i]); } static int resBuf[10000010]; static void doRound(const vector& ops, int* res) { wint((int)ops.size()); for (int x : ops) { wchar(' '); wint(x); } wchar('\n'); wflush(); for (int i = 0; i < (int)ops.size(); i++) res[i] = readInt(); } static void doRoundIgnore(const vector& ops) { if (ops.empty()) return; doRound(ops, resBuf); } static int toggle1(int v) { wint(1); wchar(' '); wint(v); wchar('\n'); wflush(); return readInt(); } static mt19937 rng(42); static void solve_small() { // Same as before: O(n^2) in one round vector ops; vector> pairs; for (int i = 1; i <= N; i++) for (int j = i+1; j <= N; j++) { ops.push_back(i); ops.push_back(j); ops.push_back(i); ops.push_back(j); pairs.push_back({i,j}); } doRound(ops, resBuf); vector> adj(N+1); for (size_t k = 0; k < pairs.size(); k++) if (resBuf[4*k+1] == 1) { adj[pairs[k].first].push_back(pairs[k].second); adj[pairs[k].second].push_back(pairs[k].first); } vector chain = {1}; if (N > 1 && !adj[1].empty()) { chain.push_back(adj[1][0]); for (int i = 2; i < N; i++) { int last = chain.back(), prev = chain[chain.size()-2]; for (int nb : adj[last]) if (nb != prev) { chain.push_back(nb); break; } } } wint(-1); for (int v : chain) { wchar(' '); wint(v); } wchar('\n'); wflush(); } // Build a large independent set using batch approach // Returns IS nodes. After return, S = IS (all IS nodes toggled on). static vector buildIS_batch(vector& allNodes) { if (allNodes.empty()) return {}; shuffle(allNodes.begin(), allNodes.end(), rng); int n = (int)allNodes.size(); set isSet; vector IS; // We process candidates in batches. Each batch: // Round 1: toggle all candidates. Find prefix before first collision. // Round 2: toggle off the non-IS part (from collision point to end). // After: S = IS vector candidates = allNodes; int maxIters = 200; // should be enough to build maximal IS for (int iter = 0; iter < maxIters && !candidates.empty(); iter++) { shuffle(candidates.begin(), candidates.end(), rng); // Round 1: toggle all candidates on doRound(candidates, resBuf); // Find first collision int j = (int)candidates.size(); for (int i = 0; i < (int)candidates.size(); i++) { if (resBuf[i] == 1) { j = i; break; } } // candidates[0..j-1] are safe (form IS with existing IS) for (int i = 0; i < j; i++) { IS.push_back(candidates[i]); isSet.insert(candidates[i]); } // Round 2: toggle off candidates[j..end] in reverse if (j < (int)candidates.size()) { vector rem; for (int i = (int)candidates.size()-1; i >= j; i--) rem.push_back(candidates[i]); doRoundIgnore(rem); } // Now S = IS // If no collision, all candidates were added - we're done if (j == (int)candidates.size()) break; // Remove IS members from candidates vector newCands; for (int v : candidates) if (!isSet.count(v)) newCands.push_back(v); // Filter: probe each candidate to check adjacency with current IS // Toggle on/off each candidate if (newCands.empty()) break; { vector ops; ops.reserve(2 * newCands.size()); for (int v : newCands) { ops.push_back(v); ops.push_back(v); } doRound(ops, resBuf); } candidates.clear(); for (int i = 0; i < (int)newCands.size(); i++) { if (resBuf[2*i] == 0) candidates.push_back(newCands[i]); } // candidates now contains only nodes not adjacent to any IS node if (candidates.empty()) break; } return IS; } static void solve_large() { vector allNodes(N); iota(allNodes.begin(), allNodes.end(), 1); // Phase 1: Build maximal IS using batch approach vector IS = buildIS_batch(allNodes); int m = (int)IS.size(); vector inIS(N+1, false); for (int v : IS) inIS[v] = true; vector nonIS; for (int v = 1; v <= N; v++) if (!inIS[v]) nonIS.push_back(v); int nm = (int)nonIS.size(); // Phase 2: Identify IS-neighbors using sum + sum-of-squares technique int bits_sum = 0; { int v = 2*m; while (v > 0) { bits_sum++; v >>= 1; } } bits_sum = max(bits_sum, 1); int bits_sq = 0; { long long v = 2LL*m*m; while (v > 0) { bits_sq++; v >>= 1; } } bits_sq = max(bits_sq, 1); vector labsq(m); for (int i = 0; i < m; i++) labsq[i] = (long long)(i+1)*(i+1); vector curLit(m, true); vector nsum(nm, 0), nsq(nm, 0); vector carry_s(nm, 0), carry_q(nm, 0); int maxBits = max(bits_sum, bits_sq); for (int b = 0; b < maxBits; b++) { if (b < bits_sum) { vector ops; ops.reserve(3*m + 4*nm); for (int i = 0; i < m; i++) { bool want = (((i+1)>>b)&1)==1; if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; } } int po1 = (int)ops.size(); for (int v : nonIS) { ops.push_back(v); ops.push_back(v); } for (int i = 0; i < m; i++) { bool want = (((i+1)>>b)&1)==0; if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; } } int po2 = (int)ops.size(); for (int v : nonIS) { ops.push_back(v); ops.push_back(v); } doRound(ops, resBuf); for (int j = 0; j < nm; j++) { int ho = resBuf[po1+2*j]; int hz = resBuf[po2+2*j]; int cnt = !ho ? 0 : !hz ? 2 : 1; int total = cnt + carry_s[j]; if (total & 1) nsum[j] |= (1LL << b); carry_s[j] = total >> 1; } } if (b < bits_sq) { vector ops; ops.reserve(3*m + 4*nm); for (int i = 0; i < m; i++) { bool want = ((labsq[i]>>b)&1)==1; if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; } } int po1 = (int)ops.size(); for (int v : nonIS) { ops.push_back(v); ops.push_back(v); } for (int i = 0; i < m; i++) { bool want = ((labsq[i]>>b)&1)==0; if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; } } int po2 = (int)ops.size(); for (int v : nonIS) { ops.push_back(v); ops.push_back(v); } doRound(ops, resBuf); for (int j = 0; j < nm; j++) { int ho = resBuf[po1+2*j], hz = resBuf[po2+2*j]; int cnt = !ho ? 0 : !hz ? 2 : 1; int total = cnt + carry_q[j]; if (total & 1) nsq[j] |= (1LL << b); carry_q[j] = total >> 1; } } } for (int j = 0; j < nm; j++) { if (carry_s[j]) nsum[j] |= ((long long)carry_s[j] << bits_sum); if (carry_q[j]) nsq[j] |= ((long long)carry_q[j] << bits_sq); } // Phase 3: Reconstruct edges from sum and sq vector> adj(N+1, {0,0}); vector deg(N+1, 0); auto addEdge = [&](int u, int v) { if (u == v || u < 1 || u > N || v < 1 || v > N) return; if (deg[u] >= 2 || deg[v] >= 2) return; for (int k = 0; k < deg[u]; k++) if (adj[u][k] == v) return; adj[u][deg[u]++] = v; adj[v][deg[v]++] = u; }; for (int j = 0; j < nm; j++) { long long S1 = nsum[j], S2 = nsq[j]; if (S1 == 0 && S2 == 0) continue; long long disc = 2*S2 - S1*S1; if (disc < 0) continue; long long d = (long long)round(sqrt((double)disc)); while (d > 0 && d*d > disc) d--; while ((d+1)*(d+1) <= disc) d++; if (d*d != disc) continue; if ((S1+d)%2 != 0) continue; long long la = (S1+d)/2, lb = (S1-d)/2; if (la >= 1 && la <= m) addEdge(nonIS[j], IS[la-1]); if (lb >= 1 && lb <= m && lb != la) addEdge(nonIS[j], IS[lb-1]); } // Phase 4: Handle remaining deg<2 nodes with second IS + binary search { vector clearOps; for (int i = 0; i < m; i++) if (curLit[i]) { clearOps.push_back(IS[i]); curLit[i] = false; } if (!clearOps.empty()) doRoundIgnore(clearOps); } vector deg1; for (int v : nonIS) if (deg[v] < 2) deg1.push_back(v); if (!deg1.empty()) { // Build IS2 among deg1 nodes using batch approach vector IS2 = buildIS_batch(deg1); int m2 = (int)IS2.size(); set is2Set(IS2.begin(), IS2.end()); vector nonIS2; for (int v : deg1) if (!is2Set.count(v)) nonIS2.push_back(v); int nm2 = (int)nonIS2.size(); if (m2 > 0 && nm2 > 0) { vector curLit2(m2, true); int bits2 = 0; { int v = m2; while (v > 0) { bits2++; v >>= 1; } } bits2 = max(bits2, 1); vector nsum2(nm2, 0); for (int b = 0; b < bits2; b++) { vector ops; ops.reserve(m2 + 2*nm2); for (int i = 0; i < m2; i++) { bool want = (((i+1)>>b)&1)==1; if (curLit2[i] != want) { ops.push_back(IS2[i]); curLit2[i] = want; } } int po = (int)ops.size(); for (int v : nonIS2) { ops.push_back(v); ops.push_back(v); } doRound(ops, resBuf); for (int j = 0; j < nm2; j++) if (resBuf[po+2*j]==1) nsum2[j] |= (1<= 1 && label <= m2) addEdge(nonIS2[j], IS2[label-1]); } } } // Traverse ring vector order; order.reserve(N); int start = 1; for (int v = 1; v <= N; v++) if (deg[v] == 2) { start = v; break; } int prev = 0, cur = start; for (int i = 0; i < N; i++) { order.push_back(cur); int nxt = (adj[cur][0] != prev) ? adj[cur][0] : adj[cur][1]; prev = cur; cur = nxt; if (cur == 0 || cur == start) break; } if ((int)order.size() != N) { order.clear(); for (int v = 1; v <= N; v++) order.push_back(v); } wint(-1); for (int v : order) { wchar(' '); wint(v); } wchar('\n'); wflush(); } int main() { int subtask = readInt(); N = readInt(); if (N <= 1) { wint(-1); wchar(' '); wint(1); wchar('\n'); wflush(); return 0; } if (N <= 1500) solve_small(); else solve_large(); return 0; }