← 返回题目列表

Codeforces · 1334/D

D. 最小欧拉循环

中文机器翻译题面 查看原题

给定一个完整的有向图 $$$K_n$$$,其中包含 $$$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$$$。

输出

对于每个测试用例,打印按字典顺序访问每个边一次的最小循环的段 $$$v_l, v_{l + 1}, \dots, v_r$$$。

示例

输入 #1

3
2 1 3
3 3 6
99995 9998900031 9998900031

输出 #1

1 2 1 
1 3 2 3 
1

注意

在第二个测试用例中,字典顺序最小循环如下所示:$$$1, 2, 1, 3, 2, 3, 1$$$。

在第三个测试用例中,很明显循环应该在顶点 $$$1$$$ 开始和结束。