AT_pakencamp_2025_day2_h Sunk Islands

**この問題はインタラクティブな問題である。** パ研洋に $ N $ 個の島が浮かんでおり、 $ 1,2,\dots,N $ と番号がつけられている。 また島同士を結ぶ $ N-1 $ 個の橋があり、 $ i $ 番目の橋は島 $ U_i $ と島 $ V_i $ を結んでいる。ここで、どの島からどの島へも橋を何回か渡ることでたどり着くことができる。 K運営長は、これらの島をすべて自身の支配下に置こうとしているが、橋の構造を知らない。そこで、橋の構造を知っているパンサーカメレオンのパ太郎に以下の質問を繰り返すことで、橋の構造を特定することにした。 1. K運営長が、島を $ 1 $ 個以上 $ N $ 個以下選び、パ太郎に伝える。 2. パ太郎は、以下の条件を満たすように $ N $ 個の島のうちいくつか沈めるとき、最大で何個の島を沈めずに残せるかをK運営長に伝える。 - 沈んでいない島はすべてK運営長によって選ばれた島である。 - どの沈んでいない島からどの沈んでいない島へも橋を何回か渡ることでたどり着くことができる。 - 沈んでいない島すべてについて、隣接する沈んでいない島は高々 $ 2 $ つである。 なお、これはパ太郎の思考実験であるため、実際に島を沈めることはない。 パ太郎も暇ではないので、 $ L $ 回までしかこの質問に答えてくれない。 パ研洋に浮かぶ島の数とパ太郎に質問できる回数が与えられたとき、どの島とどの島を結ぶ橋があるのかを求めるK運営長の戦略を実装せよ。 ### Input & Output Format 最初に、 $ N,L $ が標準入力から与えられる。 > $ N $ $ L $ 次に、あなたはパ太郎に $ L $ 回以下の質問を行う。選んだ島を島 $ s_1,s_2,\dots,s_n $ とするとき、以下の形式で出力せよ。 > ? $ n $ $ s_1 $ $ s_2 $ $ \dots $ $ s_n $ 質問すると、パ太郎からの返答が $ X $ が標準入力から与えられる。 > $ X $ ここで、 $ X $ は整数で、 - $ X\ne -1 $ のとき、質問に対する答えが $ X $ であることを表す。 - $ X=-1 $ のとき、質問した回数が $ L $ 回を超えたか、質問が形式に沿っていないことを表す。 - このとき、プログラムはすでに不正解と判定されている。ただちにプログラムを終了せよ。 橋の構造を特定することができたら、以下の形式で出力せよ。これは質問回数には計上されない。 > ! $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \dots $ $ u_{N-1} $ $ v_{N-1} $ ここで、各 $ i $ について島 $ u_i $ と島 $ v_i $ を結ぶ橋がある必要がある。また、同じ橋を複数回答えてはならない。この出力の後、ただちにプログラムを終了せよ。 上記のいずれの形式にも当てはまらない出力をした場合、`-1` が入力から与えられる。 ``` -1 ``` このときも、プログラムはすでに不正解と判定されている。ただちにプログラムを終了せよ。

N/A

N/A

### 小課題 1. ( $ 5 $ 点) $ L=33000 $ 2. ( $ 25 $ 点) $ L=10000 $ 3. ( $ 20 $ 点) $ L=6400 $ 4. ( $ 50 $ 点) $ L=4600 $ ### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力をflushせよ。そうしなかった場合、ジャッジ結果が TLE となる可能性がある。** - 解答を出力したとき、または `-1` を標準入力から受け取ったとき、ただちにプログラムを終了せよ。そうしなかった場合の判定結果は不定である。 - 余計な改行は不正なフォーマットの出力とみなされることに注意せよ。 - **この問題のジャッジシステムは適応的（adaptive）でない。** つまり、 $ U $ と $ V $ はジャッジとの対話前に決定され、いかなるタイミングでも変更されることはない。 ### 入出力例 $ N=5,U=(1,2,2,2),V=(2,3,4,5),L=10 $ のときの対話の一例を示す。 入力 出力 説明 `5 10` まず整数 $ N,L $ が標準入力から与えられる。 `? 2 1 2` $ s=(1,2) $ としてパ太郎に質問を送る。 `2` 出力は制約を満たしているので、島 $ 1,2 $ 以外を沈めるのが最適であることから $ 2 $ が与えられる。 `? 4 1 3 4 5` $ s=(1,3,4,5) $ としてパ太郎に質問を送る。 `1` 出力は制約を満たしているので、島 $ 1 $ 以外を沈めるのが最適であることから $ 1 $ が与えられる。 `? 4 2 3 4 5` $ s=(2,3,4,5) $ としてパ太郎に質問を送る。 `3` 出力は制約を満たしているので、島 $ 2,3,4 $ 以外を沈めるのが最適であることから $ 3 $ が与えられる。 `! 1 2 3 2 5 2 2 4` 橋の構造が特定できたことを報告します。この出力の後、ただちにプログラムを終了することで正解と判定される。 これは対話の一例であることに注意せよ。特に、これまでの質問とその解答で橋の構造を確実に特定できるとは限らない。 なお、このケースは制約を満たさないため、実際の採点用テストケースには含まれないことに注意せよ。 ### Constraints - $ N = 256 $ - $ 1 \leq U_i,V_i\leq N $ $ (1\leq i\leq N-1) $ - どの島からどの島へも橋を何回か渡ることでたどり着くことができる。