{"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\u003e回忆一下,当$n$是奇数时,$n$个元素的中位数的定义是:对这些元素进行排序,中位数是第$\\frac{(n+1)}{2}$大的元素。\u003c/p\u003e\n\n\u003cp\u003e在这个问题中,虽然没有给出每个元素的确切值,但给出了一些元素对之间的$m$关系。第$i$个关系可以描述为$(a_i, b_i)$,表示第$a_i$个元素严格大于第$b_i$个元素。\u003c/p\u003e\n\n\u003cp\u003e对于所有的$1 \\le k \\le n$,是否可能为每个元素分配值,使得所有关系都满足,并且第$k$个元素是$n$个元素的中位数?\u003c/p\u003e\n\n\u003ch4\u003e输入\u003c/h4\u003e\n\u003cp\u003e有多个测试用例。输入的第一行包含一个整数$T$,表示测试用例的数量。对于每个测试用例:\u003c/p\u003e\n\n\u003cp\u003e第一行包含两个整数$n$和$m$($1 \\le n \u0026lt; 100$,$1 \\le m \\le n^2$),表示元素的数量和关系的数量。保证$n$是奇数。\u003c/p\u003e\n\n\u003cp\u003e接下来的$m$行中,第$i$行包含两个整数$a_i$和$b_i$,表示第$a_i$个元素严格大于第$b_i$个元素。保证对于所有的$1 \\le i \u0026lt; j \\le m$,$a_i \\ne a_j$或$b_i \\ne b_j$。\u003c/p\u003e\n\n\u003cp\u003e保证所有测试用例的$n$的总和不会超过$2 \\times 10^3$。\u003c/p\u003e\n\n\u003ch4\u003e输出\u003c/h4\u003e\n\u003cp\u003e对于每个测试用例,输出一行,包含长度为$n$的字符串。如果可能为每个元素分配值,使得所有关系都满足,并且第$i$个元素是中位数,则字符串的第$i$个字符应为\u00271\u0027,否则应为\u00270\u0027。\u003c/p\u003e\n\n\u003ch4\u003e样例输入\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\u003e样例输出\u003c/h4\u003e\n01000\n000\n\n\u003ch4\u003e提示\u003c/h4\u003e\n\u003cp\u003e对于第一个样例测试用例,由于第2个元素小于第1个和第3个元素,并且大于第4个和第5个元素,所以可能第2个元素是中位数。\u003c/p\u003e\n\n\u003cp\u003e对于第二个样例测试用例,由于第1个元素不可能大于自身,所以不可能为元素分配值,使得所有关系都满足。\u003c/p\u003e"}}]}