#include using namespace std; using ll = long long; template istream& operator >> (istream& is, vector& vec) { for(T& x : vec) is >> x; return is; } template ostream& operator << (ostream& os, const vector& vec) { if(vec.empty()) return os; os << vec[0]; for(auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << *it; return os; } template struct xor_dsu { public: xor_dsu() : _n(0) {} xor_dsu(int n) : _n(n), num_component(n), parent_or_size(n, -1), diff_weight(n) {} bool merge(int a, int b, T w) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); w ^= diff_weight[a] ^ diff_weight[b]; if(x == y) return w == 0; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; diff_weight[y] = w; num_component--; return true; } T diff(int a, int b) { if(!same(a, b)) return -1; return diff_weight[a] ^ diff_weight[b]; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; int r = leader(parent_or_size[a]); diff_weight[a] ^= diff_weight[parent_or_size[a]]; return parent_or_size[a] = r; } int size() { return num_component; } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } private: int _n, num_component; std::vector parent_or_size; std::vector diff_weight; }; int ask(vector& x){ cout << "?"; for(auto &&v : x) cout << ' ' << v; cout << endl; string res; cin >> res; if(res == "Yes") return 1; if(res == "No") return 0; return -1; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; xor_dsu uf(n + 1); vector> edge(n - 1); for(auto &&[u, v] : edge){ cin >> u >> v; uf.merge(u, v, 1); } vector x(n - 1); for(int i = 0; i + 1 < n; i++){ auto [u, v] = edge[i]; if(uf.diff(u, 1) == 0) x[i] = u; else x[i] = v; } int res = ask(x); assert(res != -1); vector able(n + 1); for(int i = 0; i + 1 < n; i++){ auto [u, v] = edge[i]; if(res ^ uf.diff(u, 1)){ able[u] = true; }else{ able[v] = true; } } //cout << able << '\n'; while(count(able.begin(), able.end(), true) >= 2){ int sg = 1; vector tr(n + 1); for(int v = 1; v <= n; v++){ if(!able[v]) continue; if(sg) tr[v] = true; sg ^= 1; } for(int i = 0; i + 1 < n; i++){ auto [u, v] = edge[i]; if(tr[u]){ x[i] = u; continue; } if(able[v]){ if(tr[v]) x[i] = v; else x[i] = u; }else{ x[i] = v; } } int res = ask(x); assert(res != -1); for(int v = 1; v <= n; v++){ if(!able[v]) continue; // res == 1 のときtr[v] == falseを落とす // res == 0 のときtr[v] == trueを落とす if(tr[v] ^ res){ able[v] = false; } } //cout << able << '\n'; } cout << "! " << (int)(find(able.begin(), able.end(), true) - able.begin()) << endl; }