{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eRecall the definition of the median of $n$ elements where $n$ is odd: sort these elements and the median is the $\\frac{(n+1)}{2}$-th largest element.\u003c/p\u003e\n\n\u003cp\u003eIn this problem, the exact value of each element is not given, but $m$ relations between some pair of elements are given. The $i$-th relation can be described as $(a_i, b_i)$, which indicates that the $a_i$-th element is strictly larger than the $b_i$-th element.\u003c/p\u003e\n\n\u003cp\u003eFor all $1 \\le k \\le n$, is it possible to assign values to each element so that all the relations are satisfied and the $k$-th element is the median of the $n$ elements?\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains two integers $n$ and $m$ ($1 \\le n \u0026lt; 100$, $1 \\le m \\le n^2$), indicating the number of elements and the number of relations. It\u0027s guaranteed that $n$ is odd.\u003c/p\u003e\n\n\u003cp\u003eFor the following $m$ lines, the $i$-th line contains two integers $a_i$ and $b_i$, indicating that the $a_i$-th element is strictly larger than the $b_i$-th element. It guaranteed that for all $1 \\le i \u0026lt; j \\le m$, $a_i \\ne a_j$ or $b_i \\ne b_j$.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ of all test cases will not exceed $2 \\times 10^3$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one string of length $n$. If it is possible to assign values to each element so that all the relations are satisfied and the $i$-th element is the median, the $i$-th character of the string should be \u00271\u0027, otherwise it should be \u00270\u0027.\u003c/p\u003e\n\n\u003ch4\u003eSample Input\u003c/h4\u003e\n\u003cpre\u003e2\n5 4\n1 2\n3 2\n2 4\n2 5\n3 2\n1 1\n2 3\n\u003c/pre\u003e\n\n\u003ch4\u003eSample Output\u003c/h4\u003e\n01000\n000\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first sample test case, as the 2nd element is smaller than the 1st and the 3rd elements and is larger than the 4th and the 5th elements, it\u0027s possible that the 2nd element is the median.\u003c/p\u003e\n\n\u003cp\u003eFor the second sample test case, as the 1st element can\u0027t be larger than itself, it\u0027s impossible to assign values to the elements so that all the relations are satisfied.\u003c/p\u003e\n"}}]}