CF1334D Minimum Euler Cycle

给定一个有 $n$ 个顶点的完全有向图 $K_n$：对于 $K_n$ 中的每一对不同顶点 $u \neq v$，都存在有向边 $(u, v)$ 和 $(v, u)$，且没有自环。 你需要在 $K_n$ 中找到一个经过每条有向边恰好一次的回路（允许重复经过顶点）。 我们可以将这样的回路表示为一个长度为 $n(n-1)+1$ 的顶点序列 $v_1, v_2, v_3, \dots, v_{n(n-1)-1}, v_{n(n-1)}, v_{n(n-1)+1}=v_1$，即访问顺序，其中每条有向边 $(v_i, v_{i+1})$ 恰好出现一次。 请你找到字典序最小的这样的回路。可以证明，这样的回路总是存在的。 由于答案可能过大，请只输出其第 $[l, r]$ 段，即 $v_l, v_{l+1}, \dots, v_r$。

第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试用例的数量。 接下来的 $T$ 行，每行一个测试用例。每个测试用例包含三个整数 $n$、$l$ 和 $r$（$2 \le n \le 10^5$，$1 \le l \le r \le n(n-1)+1$，$r-l+1 \le 10^5$），分别表示 $K_n$ 的顶点数，以及需要输出的回路区间。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，所有测试用例中 $r-l+1$ 的总和不超过 $10^5$。

对于每个测试用例，输出字典序最小的、经过每条有向边恰好一次的回路的第 $l$ 到 $r$ 个顶点（$v_l, v_{l+1}, \dots, v_r$）。

在第二个测试用例中，字典序最小的回路为：$1, 2, 1, 3, 2, 3, 1$。 在第三个测试用例中，很明显回路应该从顶点 $1$ 开始并以顶点 $1$ 结束。 由 ChatGPT 4.1 翻译