{"problem":{"name":"Appraiser","description":{"content":"This problem is **interactive**, and the **judge is adaptive**. See the notes for details.   **Also, the parameters in the problem statement are fixed at $N=1000$, $M=10$, $Q=950$.** There are $N$ coi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc184_a"},"statements":[{"statement_type":"Markdown","content":"This problem is **interactive**, and the **judge is adaptive**. See the notes for details.  \n**Also, the parameters in the problem statement are fixed at $N=1000$, $M=10$, $Q=950$.**\nThere are $N$ coins numbered $1, 2, \\dots, N$.  \nExactly $M$ of these coins are counterfeit.\nAn appraiser can, in one appraisal, determine whether two coins are of the same type or different types. Specifically:\n\n*   If the two coins are both genuine or both counterfeit, they are judged to be of the same type.\n*   Otherwise, they are judged to be of different types.\n\nIdentify all the counterfeit coins using at most $Q$ appraisals.\n\n## Constraints\n\n*   $\\color{red}{N = 1000}$\n*   $\\color{red}{M = 10}$\n*   $\\color{red}{Q = 950}$\n\n## Interaction\n\nThis is an interactive problem.  \nInitially, receive $N$, $M$, and $Q$ from Standard Input:\n\n$N$ $M$ $Q$\n\n  \n\nNext, you can perform appraisals between $0$ and $Q$ times, inclusive, as follows.\nFirst, by outputting to Standard Output in the following format, you indicate that you are appraising coins $x$ and $y$. (Include a newline at the end.)\n\n? $x$ $y$\n\nHere, $x$ and $y$ must be distinct integers between $1$ and $N$, inclusive.\nIn response, the judge system will reply with one of the following three responses.\n\n0\n\nIf the response is `0`, it means that coins $x$ and $y$ are of the same type.\n\n1\n\nIf the response is `1`, it means that coins $x$ and $y$ are of different types.\n\n\\-1\n\nIf the response is `-1`, it means that the appraisal is invalid. Specifically, this response is given when at least one of the following conditions is met:\n\n*   The outputted $x$ and $y$ does not satisfy the constraints.\n*   The number of appraisals exceeds $Q$.\n\nIf you receive this response, your program is considered incorrect. Terminate your program immediately.\n  \n\nFinally, by outputting to Standard Output in the following format, you answer that coins $A_1, A_2, \\dots, A_{M}$ are counterfeit. (Include a newline at the end.)\n\n! $A_1$ $A_2$ $\\dots$ $A_{M}$\n\nHere, $A_i$ must be distinct integers between $1$ and $N$, inclusive.  \nAfter this output, terminate your program immediately.\nIf any of your outputs do not meet the specified format, your program will be considered incorrect. The judge will then respond with `-1`, so in that case, terminate your program immediately.\n\n[samples]\n\n## Notes\n\n*   **Every time you output, include a newline at the end and flush Standard Output.** Failure to do so may result in a verdict of TLE or WA.\n*   After outputting your answer (or receiving `-1`), terminate your program immediately. Otherwise, the verdict is indeterminate.\n*   Beware that unnecessary newlines are considered as malformed.\n*   **The judge for this problem is adaptive.** That is, at any point, as long as consistency can be maintained, the judge may change which coins are counterfeit. See the sample interaction for details.","is_translate":false,"language":"English"}],"meta":{"iden":"arc184_a","tags":[],"sample_group":[],"created_at":"2026-03-03 11:01:14"}}