P15775 [JAG 2025 Summer Camp #2] Hanako' s Art II

在 $xy$ 平面上有 $2n$ 个点。任意两个点的 $x$ 坐标和 $y$ 坐标均不相同。每个点有一个颜色，用 $1$ 到 $n$（含）之间的整数表示。对于 $n$ 种颜色中的每一种，恰好有两个点具有该颜色。 一位艺术家 Hanako 打算通过在 $xy$ 平面上绘制 $n$ 条折线来创作一幅杰作。根据她的审美观，一幅杰作必须满足以下所有条件： - 任何两个颜色相同的点必须是某条折线的两个端点。 - 每条折线恰好由两条线段组成，每条线段平行于 $x$ 轴或 $y$ 轴。 - 任意两条折线不相交。 你的任务是判断 Hanako 能否创作出这样一幅杰作。

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 50\,000$），表示测试用例的数量。随后是 $t$ 个测试用例。每个测试用例的格式如下： $$ \begin{aligned} & n \\ & y_1 \ c_1 \\ & \vdots \\ & y_{2n} \ c_{2n} \end{aligned} $$ 第一行包含一个整数 $n$（$1 \leq n \leq 1\,000$），表示 Hanako 需要绘制的折线数量。接下来的 $2n$ 行，每行包含两个整数 $y_i$ 和 $c_i$，满足 $1 \leq y_i \leq 2n$ 且 $1 \leq c_i \leq n$。每行表示第 $i$ 个点的坐标为 $(i, y_i)$，颜色为 $c_i$。 保证当 $i \neq j$ 时 $y_i \neq y_j$。此外，没有三个点具有相同的颜色。 所有测试用例的 $n^2$ 之和不超过 $10^6$。

如果 Hanako 能够创作出杰作，输出 "Yes"；否则，输出 "No"。

样例输入 1 中一种可能的杰作如图 J-1 所示。 :::align{center}  图 J-1：样例输入 1 的示意图 ::: 翻译由 DeepSeek V3.2 完成