#include #include #include #include #include #include #include using namespace std; int n; vector> adj; vector do_query(const vector& q) { if (q.empty()) { return {}; } cout << q.size(); for (int x : q) { cout << " " << x; } cout << endl; vector res(q.size()); for (size_t i = 0; i < q.size(); ++i) { cin >> res[i]; } return res; } struct Ask { vector p1, p2; vector p1_res_indices; vector p2_res_indices; }; void solve(const vector& pids, int level, vector>& level_asks) { if (pids.size() <= 1) { return; } if (pids.size() <= 32) { // Base case for (size_t i = 0; i < pids.size(); ++i) { for (size_t j = i + 1; j < pids.size(); ++j) { level_asks[level].push_back({{pids[i]}, {pids[j]}}); } } return; } vector pids1(pids.begin(), pids.begin() + pids.size() / 2); vector pids2(pids.begin() + pids.size() / 2, pids.end()); solve(pids1, level + 1, level_asks); solve(pids2, level + 1, level_asks); map> current_adj; for (int pid : pids) { for (int neighbor : adj[pid]) { current_adj[pid].push_back(neighbor); } } vector> pids1_parts(2), pids2_parts(2); map pids1_color_map, pids2_color_map; auto find_components_and_color = [&](const vector& component_pids, map& color_map) { map visited; for (int pid : component_pids) { if (!visited[pid]) { vector component_nodes; vector q_bfs; q_bfs.push_back(pid); visited[pid] = true; int head = 0; while(head < q_bfs.size()){ int u = q_bfs[head++]; component_nodes.push_back(u); for(int v : current_adj[u]){ bool is_in_pids = false; for(int p : component_pids) if(v == p) is_in_pids = true; if(is_in_pids && !visited[v]){ visited[v] = true; q_bfs.push_back(v); } } } function_dfs = [&](int u, int c) { color_map[u] = c; for (int v : current_adj[u]) { bool is_in_component = false; for(int node : component_nodes) if(v == node) is_in_component = true; if (is_in_component && color_map[v] == 0) { _dfs(v, 3 - c); } } }; _dfs(pid, 1); } } }; find_components_and_color(pids1, pids1_color_map); find_components_and_color(pids2, pids2_color_map); for (int pid : pids1) pids1_parts[pids1_color_map[pid] - 1].push_back(pid); for (int pid : pids2) pids2_parts[pids2_color_map[pid] - 1].push_back(pid); for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { if (!pids1_parts[i].empty() && !pids2_parts[j].empty()) { level_asks[level].push_back({pids1_parts[i], pids2_parts[j]}); level_asks[level].push_back({pids2_parts[j], pids1_parts[i]}); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int subtask; cin >> subtask >> n; adj.resize(n + 1); int max_levels = 0; if (n > 1) max_levels = floor(log2(n/16.0)) + 2; if (n <= 32) max_levels = 1; vector> level_asks(max_levels); vector all_pids(n); iota(all_pids.begin(), all_pids.end(), 1); if (n > 1) { solve(all_pids, 0, level_asks); } for (int l = max_levels - 1; l >= 0; --l) { if(level_asks[l].empty()) continue; vector query_vec; size_t current_res_idx = 0; for (auto& ask : level_asks[l]) { vector p1 = ask.p1, p2 = ask.p2; query_vec.insert(query_vec.end(), p1.begin(), p1.end()); query_vec.insert(query_vec.end(), p2.begin(), p2.end()); for (size_t i = 0; i < p1.size(); ++i) ask.p1_res_indices.push_back(current_res_idx + i); current_res_idx += p1.size(); for (size_t i = 0; i < p2.size(); ++i) ask.p2_res_indices.push_back(current_res_idx + i); current_res_idx += p2.size(); } vector full_query = query_vec; vector query_vec_rev = query_vec; reverse(query_vec_rev.begin(), query_vec_rev.end()); full_query.insert(full_query.end(), query_vec_rev.begin(), query_vec_rev.end()); vector responses = do_query(full_query); vector has_adj_res(responses.begin(), responses.begin() + query_vec.size()); vector>> specific_neighbor_queries; for (const auto& ask : level_asks[l]) { if (ask.p1.size() == 1 && ask.p2.size() == 1) { // Base case if (has_adj_res[ask.p2_res_indices[0]] == 1) { adj[ask.p1[0]].push_back(ask.p2[0]); adj[ask.p2[0]].push_back(ask.p1[0]); } continue; } bool p1_has_adj = (ask.p1.empty() || ask.p1_res_indices.empty()) ? false : (bool)has_adj_res[ask.p1_res_indices.back()]; int last_res = p1_has_adj; for (size_t i = 0; i < ask.p2.size(); ++i) { int current_res = has_adj_res[ask.p2_res_indices[i]]; if (current_res == 1 && last_res == 0) { specific_neighbor_queries.push_back({ask.p2[i], ask.p1}); } last_res = current_res; } } if (!specific_neighbor_queries.empty()) { vector big_q; vector, int>> q_meta; for(const auto& sq : specific_neighbor_queries) { big_q.push_back(sq.first); big_q.insert(big_q.end(), sq.second.begin(), sq.second.end()); q_meta.emplace_back(sq.first, sq.second, big_q.size() - 1); big_q.insert(big_q.end(), sq.second.rbegin(), sq.second.rend()); big_q.push_back(sq.first); } vector res_big_q = do_query(big_q); int base_idx = 0; for(const auto& meta : q_meta) { int u = get<0>(meta); const vector& p = get<1>(meta); int u_on_idx = base_idx; int last_res = res_big_q[u_on_idx]; for (size_t i = 0; i < p.size(); ++i) { int current_res = res_big_q[u_on_idx + 1 + i]; if (current_res == 1 && last_res == 0) { int v = p[i]; adj[u].push_back(v); adj[v].push_back(u); } last_res = current_res; } base_idx += 2 * p.size() + 2; } } } cout << -1; vector p; if (n > 0) { p.resize(n); p[0] = 1; if (n > 1) { p[1] = adj[1][0]; for (int i = 2; i < n; ++i) { int last = p[i - 1]; int prev = p[i - 2]; for (int neighbor : adj[last]) { if (neighbor != prev) { p[i] = neighbor; break; } } } } } for (int i = 0; i < n; ++i) { cout << " " << p[i]; } cout << endl; return 0; }