| |
| #include <bits/stdc++.h> |
| 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<int>& 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<int>& ops) { |
| if (ops.empty()) return; |
| doRound(ops, resBuf); |
| } |
|
|
| static mt19937 rng(42); |
|
|
| static void solve_large() { |
| vector<int> allNodes(N); |
| iota(allNodes.begin(), allNodes.end(), 1); |
| shuffle(allNodes.begin(), allNodes.end(), rng); |
|
|
| |
| vector<int> IS; |
| set<int> isSet; |
| vector<int> candidates = allNodes; |
|
|
| int total_rounds = 0; |
| long long total_queries = 0; |
|
|
| for (int iter = 0; iter < 500 && !candidates.empty(); iter++) { |
| shuffle(candidates.begin(), candidates.end(), rng); |
| doRound(candidates, resBuf); |
| total_rounds++; |
| total_queries += candidates.size(); |
|
|
| int j = (int)candidates.size(); |
| for (int i = 0; i < (int)candidates.size(); i++) { |
| if (resBuf[i] == 1) { j = i; break; } |
| } |
|
|
| for (int i = 0; i < j; i++) { |
| IS.push_back(candidates[i]); |
| isSet.insert(candidates[i]); |
| } |
|
|
| if (j < (int)candidates.size()) { |
| vector<int> rem; |
| for (int i = (int)candidates.size()-1; i >= j; i--) |
| rem.push_back(candidates[i]); |
| doRoundIgnore(rem); |
| total_rounds++; |
| total_queries += rem.size(); |
| } |
|
|
| if (j == (int)candidates.size()) break; |
|
|
| vector<int> remaining; |
| for (int v : candidates) if (!isSet.count(v)) remaining.push_back(v); |
| if (remaining.empty()) break; |
|
|
| { |
| vector<int> ops; |
| ops.reserve(2*remaining.size()); |
| for (int v : remaining) { ops.push_back(v); ops.push_back(v); } |
| doRound(ops, resBuf); |
| total_rounds++; |
| total_queries += ops.size(); |
| } |
| candidates.clear(); |
| for (int i = 0; i < (int)remaining.size(); i++) { |
| if (resBuf[2*i] == 0) candidates.push_back(remaining[i]); |
| } |
|
|
| fprintf(stderr, "Phase1 iter %d: IS=%d, candidates=%d\n", iter, (int)IS.size(), (int)candidates.size()); |
| } |
|
|
| int m = (int)IS.size(); |
| fprintf(stderr, "Phase 1 done: IS=%d, rounds=%d, queries=%lld\n", m, total_rounds, total_queries); |
|
|
| vector<bool> inIS(N+1, false); |
| for (int v : IS) inIS[v] = true; |
|
|
| vector<int> nonIS; |
| for (int v = 1; v <= N; v++) if (!inIS[v]) nonIS.push_back(v); |
| int nm = (int)nonIS.size(); |
|
|
| |
| 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); |
|
|
| fprintf(stderr, "Phase 2: bits_sum=%d, bits_sq=%d, m=%d, nm=%d\n", bits_sum, bits_sq, m, nm); |
|
|
| vector<long long> labsq(m); |
| for (int i = 0; i < m; i++) labsq[i] = (long long)(i+1)*(i+1); |
|
|
| vector<bool> curLit(m, true); |
| vector<long long> nsum(nm, 0), nsq(nm, 0); |
| vector<int> 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<int> 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); |
| total_rounds++; |
| total_queries += ops.size(); |
|
|
| 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<int> 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); |
| total_rounds++; |
| total_queries += ops.size(); |
|
|
| 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); |
| } |
|
|
| fprintf(stderr, "Phase 2 done: rounds=%d, queries=%lld\n", total_rounds, total_queries); |
|
|
| |
| vector<array<int,2>> adj(N+1, {0,0}); |
| vector<int> 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; |
| }; |
|
|
| int edges_found = 0; |
| int edges_failed = 0; |
| for (int j = 0; j < nm; j++) { |
| long long S1 = nsum[j], S2 = nsq[j]; |
| if (S1 == 0 && S2 == 0) { edges_failed++; continue; } |
| long long disc = 2*S2 - S1*S1; |
| if (disc < 0) { edges_failed++; 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) { edges_failed++; continue; } |
| if ((S1+d)%2 != 0) { edges_failed++; continue; } |
| long long la = (S1+d)/2, lb = (S1-d)/2; |
| int added = 0; |
| if (la >= 1 && la <= m) { addEdge(nonIS[j], IS[la-1]); added++; } |
| if (lb >= 1 && lb <= m && lb != la) { addEdge(nonIS[j], IS[lb-1]); added++; } |
| edges_found += added; |
| } |
|
|
| fprintf(stderr, "Phase 3: edges_found=%d, edges_failed=%d\n", edges_found, edges_failed); |
|
|
| |
| int d0=0, d1=0, d2=0; |
| for (int v = 1; v <= N; v++) { |
| if (deg[v] == 0) d0++; |
| else if (deg[v] == 1) d1++; |
| else d2++; |
| } |
| fprintf(stderr, "Deg distribution: d0=%d, d1=%d, d2=%d\n", d0, d1, d2); |
|
|
| |
| { |
| vector<int> clearOps; |
| for (int i = 0; i < m; i++) |
| if (curLit[i]) { clearOps.push_back(IS[i]); curLit[i] = false; } |
| if (!clearOps.empty()) doRoundIgnore(clearOps); |
| total_rounds++; |
| total_queries += clearOps.size(); |
| } |
|
|
| vector<int> deg1; |
| for (int v : nonIS) if (deg[v] < 2) deg1.push_back(v); |
| fprintf(stderr, "Phase 4: deg1 nodes=%d\n", (int)deg1.size()); |
|
|
| if (!deg1.empty()) { |
| shuffle(deg1.begin(), deg1.end(), rng); |
| vector<int> IS2; |
| set<int> is2Set; |
| vector<int> candidates = deg1; |
|
|
| for (int iter = 0; iter < 300 && !candidates.empty(); iter++) { |
| shuffle(candidates.begin(), candidates.end(), rng); |
| doRound(candidates, resBuf); |
| total_rounds++; |
| total_queries += candidates.size(); |
|
|
| int j2 = (int)candidates.size(); |
| for (int i = 0; i < (int)candidates.size(); i++) { |
| if (resBuf[i] == 1) { j2 = i; break; } |
| } |
| for (int i = 0; i < j2; i++) { |
| IS2.push_back(candidates[i]); |
| is2Set.insert(candidates[i]); |
| } |
| if (j2 < (int)candidates.size()) { |
| vector<int> rem; |
| for (int i = (int)candidates.size()-1; i >= j2; i--) |
| rem.push_back(candidates[i]); |
| doRoundIgnore(rem); |
| total_rounds++; |
| total_queries += rem.size(); |
| } |
| if (j2 == (int)candidates.size()) break; |
|
|
| vector<int> remaining; |
| for (int v : candidates) if (!is2Set.count(v)) remaining.push_back(v); |
| if (remaining.empty()) break; |
|
|
| { |
| vector<int> ops; |
| ops.reserve(2*remaining.size()); |
| for (int v : remaining) { ops.push_back(v); ops.push_back(v); } |
| doRound(ops, resBuf); |
| total_rounds++; |
| total_queries += ops.size(); |
| } |
| candidates.clear(); |
| for (int i = 0; i < (int)remaining.size(); i++) { |
| if (resBuf[2*i] == 0) candidates.push_back(remaining[i]); |
| } |
| } |
|
|
| int m2 = (int)IS2.size(); |
| vector<int> nonIS2; |
| for (int v : deg1) if (!is2Set.count(v)) nonIS2.push_back(v); |
| int nm2 = (int)nonIS2.size(); |
| fprintf(stderr, "Phase 4: IS2=%d, nonIS2=%d\n", m2, nm2); |
|
|
| if (m2 > 0 && nm2 > 0) { |
| vector<bool> curLit2(m2, true); |
| int bits2 = 0; |
| { int v = m2; while (v > 0) { bits2++; v >>= 1; } } |
| bits2 = max(bits2, 1); |
| vector<int> nsum2(nm2, 0); |
|
|
| for (int b = 0; b < bits2; b++) { |
| vector<int> 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); |
| total_rounds++; |
| total_queries += ops.size(); |
| for (int j = 0; j < nm2; j++) |
| if (resBuf[po+2*j]==1) nsum2[j] |= (1<<b); |
| } |
| int ph4_found = 0; |
| for (int j = 0; j < nm2; j++) { |
| int label = nsum2[j]; |
| if (label >= 1 && label <= m2) { addEdge(nonIS2[j], IS2[label-1]); ph4_found++; } |
| } |
| fprintf(stderr, "Phase 4 binary search: found=%d\n", ph4_found); |
| } |
| } |
|
|
| |
| d0=0; d1=0; d2=0; |
| for (int v = 1; v <= N; v++) { |
| if (deg[v] == 0) d0++; |
| else if (deg[v] == 1) d1++; |
| else d2++; |
| } |
| fprintf(stderr, "Final deg: d0=%d, d1=%d, d2=%d\n", d0, d1, d2); |
| fprintf(stderr, "Total rounds=%d, queries=%lld\n", total_rounds, total_queries); |
|
|
| |
| vector<int> 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; |
| } |
| fprintf(stderr, "Traversal length: %d / %d\n", (int)order.size(), N); |
| 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_large(); |
| } |
| else solve_large(); |
| return 0; |
| } |
|
|
