P14053 [SDCPC 2019] Median

回忆一下 $n$ 个元素（$n$ 为奇数）的中位数的定义：将这些元素排序后，中位数是第 $\frac{(n+1)}{2}$ 大的元素。 本题中，每个元素的具体数值未知，但给出了 $m$ 个元素两两之间的关系。第 $i$ 个关系记为 $(a_i, b_i)$，表示第 $a_i$ 个元素严格大于第 $b_i$ 个元素。 对于所有 $1 \le k \le n$，问能否给每个元素赋值，使得所有的大小关系都成立，并且第 $k$ 个元素为这 $n$ 个元素的中位数？

有多组测试数据。输入的第一行为整数 $T$，表示测试数据组数。对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$（$1 \le n < 100$，$1 \le m \le n^2$），分别表示元素个数和关系个数。保证 $n$ 为奇数。 接下来的 $m$ 行，每行两个整数 $a_i$ 和 $b_i$，表示第 $a_i$ 个元素严格大于第 $b_i$ 个元素。保证对任意 $1 \le i < j \le m$，有 $a_i \ne a_j$ 或 $b_i \ne b_j$。 保证所有测试数据的 $n$ 之和不超过 $2 \times 10^3$。

对于每组测试数据，输出一行长度为 $n$ 的字符串。如果存在满足所有关系且第 $i$ 个元素为中位数的赋值方案，则字符串第 $i$ 个字符为 `1`，否则为 `0`。

对于第一个样例测试，2 号元素比 1 号和 3 号元素小、比 4 号和 5 号元素大，因此可以为中位数。 对于第二个样例测试，1 号元素不可能比自己大，因此无法给元素赋值使得所有关系都成立。 由 ChatGPT 5 翻译