{"raw_statement":[{"iden":"problem statement","content":"Huge kingdom: $Atcoder$ contains $N$ towns and $N-1$ roads. This kingdom is connected.  \n  \nYou have to detect the kingdom's road.  \nIn order to detect, You can ask this form of questions.  \n\n*   You can output a string $S$. Length of $S$ must be $N$ and The character of string $S$ must be represented by '$0$' or '$1$'.\n*   Computer paint the towns with white or black according to the character string you output.\n*   If $i$-th character of $S$ is '0', computer paint town $i$ white.\n*   If $i$-th character of $S$ is '1', computer paint town $i$ black.\n*   Please consider an undirected graph $G$.\n*   For each edge, computer do the following processing: If both ends painted black, computer adds this edge to $G$.\n*   Computer returns value $x$: sum of \"diameter of tree\"$^2$ about each connected components.\n\nFor example, when $S$=\"11001111\" and the kingdom's structure is this, computer returns 10.  \n\n![image](https://atcoder.jp/img/s8pc-4/18f55c17e4feefd6794b69a1b91d5e6f.png)\n\nPlease detect the structure of $Atcoder$ as few questions as possible."},{"iden":"input, output","content":"This is a reactive problem.  \nThe first input is as follows:  \n  \n\n> $N$\n\n*   $N$ is number of towns in $Atcoder$.\n\n  \nNext, you can ask questions.  \nThe question must be in the form as follows:  \n\n> ? $S$\n\n$S$ is a string. The mean of $S$ written in the problem statement. Length of $S$ must be $N$.  \n  \nThe answer of question is as follows:  \n\n> $x$\n\nThe mean of $x$ written in the problem statement.  \n  \nFinally, your program must output as follows:  \n\n> ! $(a_1,b_1)$ $(a_2,b_2)$ $(a_3,b_3)$ … $(a_{N-1},b_{N-1})$\n\nThis output means your program detects all roads of $Atcoder$.  \n$(a_i,b_i)$ means there is a road between $a_i$ and $b_i$.  \n  \nYou can output roads any order, but you must output the answer on a single line."},{"iden":"constraints","content":"*   $N$=200\n*   $Atcoder$ contains $N-1$ roads and this kingdom is connected.\n*   All cases were made randomly."},{"iden":"scoring","content":"Let the number of questions be $L$.  \n  \n\n*   If $L > 20000$, $score$ = $0$ points\n*   If $18000 < L ≦ 20000$, $score$ = $200$ points\n*   If $5000 < L ≦ 18000$, $score$ = $650-L/40$ points\n*   If $4000 < L ≦ 5000$, $score$ = $800-L/20$ points\n*   If $2000 < L ≦ 4000$, $score$ = $1400-L/5$ points\n*   If $1200 < L ≦ 2000$, $score$ = $1500-L/4$ points\n*   If $700 < L ≦ 1200$, $score$ = $1850-L/2$ points\n*   If $L ≦ 700$, $score$ = $1500$ points\n\n  \nThere is $5$ cases, so points of each case is $score/5$."},{"iden":"sample input","content":"This case is $N=4$. This case is not include because this is not $N=200$.  \n\nN=4\n0 1\n1 2\n1 3"},{"iden":"sample output","content":"Sample interaction is as follows:  \n\nInput from computer\n\nOutput\n\n4\n\n? 1111\n\n4\n\n? 1101\n\n4\n\n? 1001\n\n0\n\n? 1100\n\n1\n\n? 1011\n\n0\n\n! (0,1) (1,2) (1,3)\n\n  \nIn this sample, structure of $Atcoder$ is as follows:  \n\n![image](https://atcoder.jp/img/s8pc-4/8d26e2d0a3fd5e4cc24efe8d21296341.png)\n\n  \nThis question is not always meaningful."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}