#line 1 "library/Template/template.hpp" #include using namespace std; #define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rrep(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--) #define ALL(v) (v).begin(), (v).end() #define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin()) #define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin()) using uint = unsigned int; using ll = long long int; using ull = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; template S SUM(const vector &a) { return accumulate(ALL(a), S(0)); } template S POW(S a, T b) { S ret = 1, base = a; for (;;) { if (b & 1) ret *= base; b >>= 1; if (b == 0) break; base *= base; } return ret; } template inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } template T ceil(T x, U y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x > 0 ? (x + y - 1) / y : x / y); } template T floor(T x, U y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x > 0 ? x / y : (x - y + 1) / y); } template int popcnt(T x) { return __builtin_popcountll(x); } template int topbit(T x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } template int lowbit(T x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template ostream &operator<<(ostream &os, const pair &p) { os << "P(" << p.first << ", " << p.second << ")"; return os; } template ostream &operator<<(ostream &os, const vector &vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } template ostream &operator<<(ostream &os, const map &map_var) { os << "{"; for (auto itr = map_var.begin(); itr != map_var.end(); itr++) { os << "(" << itr->first << ", " << itr->second << ")"; itr++; if (itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } template ostream &operator<<(ostream &os, const set &set_var) { os << "{"; for (auto itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } #ifdef LOCAL #define debug 1 #define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__) #else #define debug 0 #define show(...) true #endif template void _show(int i, T name) { cerr << '\n'; } template void _show(int i, const T1 &a, const T2 &b, const T3 &...c) { for (; a[i] != ',' && a[i] != '\0'; i++) cerr << a[i]; cerr << ":" << b << " "; _show(i + 1, a, c...); } #line 2 "sol.cpp" // #include "Utility/fastio.hpp" #line 2 "library/Utility/random.hpp" namespace Random { mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count()); using u64 = unsigned long long; u64 get() { return randgen(); } template T get(T L) { // [0,L] return get() % (L + 1); } template T get(T L, T R) { // [L,R] return get(R - L) + L; } double uniform() { return double(get(1000000000)) / 1000000000; } string str(int n) { string ret; rep(i, 0, n) ret += get('a', 'z'); return ret; } template void shuffle(Iter first, Iter last) { if (first == last) return; int len = 1; for (auto it = first + 1; it != last; it++) { len++; int j = get(0, len - 1); if (j != len - 1) iter_swap(it, first + j); } } template vector select(int n, T L, T R) { // [L,R] if (n * 2 >= R - L + 1) { vector ret(R - L + 1); iota(ALL(ret), L); shuffle(ALL(ret)); ret.resize(n); return ret; } else { unordered_set used; vector ret; while (SZ(used) < n) { T x = get(L, R); if (!used.count(x)) { used.insert(x); ret.push_back(x); } } return ret; } } void relabel(int n, vector> &es) { shuffle(ALL(es)); vector ord(n); iota(ALL(ord), 0); shuffle(ALL(ord)); for (auto &[u, v] : es) u = ord[u], v = ord[v]; } template vector> genGraph(int n, int m) { vector> cand, es; rep(u, 0, n) rep(v, 0, n) { if (!self and u == v) continue; if (!directed and u > v) continue; cand.push_back({u, v}); } if (m == -1) m = get(SZ(cand)); // chmin(m, SZ(cand)); vector ord; if (multi) rep(_, 0, m) ord.push_back(get(SZ(cand) - 1)); else { ord = select(m, 0, SZ(cand) - 1); } for (auto &i : ord) es.push_back(cand[i]); relabel(n, es); return es; } vector> genTree(int n) { vector> es; rep(i, 1, n) es.push_back({get(i - 1), i}); relabel(n, es); return es; } }; // namespace Random /** * @brief Random */ #line 4 "sol.cpp" int main() { int n; cin >> n; vector g(n, vector()); using P = pair; vector

es; rep(_, 0, n - 1) { int x, y; cin >> x >> y; x--, y--; es.push_back({x, y}); g[x].push_back(y); g[y].push_back(x); } int god = Random::get(1, n); auto ask = [&](vector &X) -> bool { cout << "? "; rep(i, 0, n - 1) { cout << X[i] + 1 << ' '; assert(X[i] == es[i].first or X[i] == es[i].second); } cout << endl; if (debug) { bool ch = 0; for (auto &x : X) if (god == x) ch = 1; show(ch); return ch; } string s; cin >> s; assert(s != "Invalid"); return s == "Yes"; }; vector col(n); auto dfs = [&](auto &dfs, int v, int p) -> void { for (auto &to : g[v]) if (to != p) { col[to] = col[v] ^ 1; dfs(dfs, to, v); } }; col[0] = 0; dfs(dfs, 0, -1); int which = -1; { vector C(n - 1); rep(i, 0, n - 1) { if (col[es[i].first]) C[i] = es[i].first; else C[i] = es[i].second; } if (ask(C)) which = 1; else which = 0; } vector cand; rep(i, 0, n) if (col[i] == which) cand.push_back(i); while (SZ(cand) > 1) { rep(i, 0, n) col[i] = -1; for (auto &v : cand) col[v] = 0; rep(i, 0, SZ(cand) / 2) { col[cand[i]] = 1; } show(col); vector que; for (auto &[u, v] : es) { assert(col[u] == -1 or col[v] == -1); if (col[u] == 1) que.push_back(u); else if (col[u] == 0) que.push_back(v); else if (col[v] == 1) que.push_back(v); else if (col[v] == 0) que.push_back(u); else que.push_back(u); } which = -1; if (ask(que)) which = 1; else which = 0; vector nxt; for (auto &v : cand) if (col[v] == which) { nxt.push_back(v); } swap(cand, nxt); } cout << "! " << cand[0] + 1 << endl; if (debug) { assert(god == cand[0]); } return 0; }