← 返回题目列表

Codeforces · 2110/E

E. 旋律

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

2077 年,统治世界的机器人意识到人类的音乐并不是那么好,所以他们开始创作自己的音乐。

为了写音乐,机器人有一种特殊的乐器,能够产生 $$$n$$$ 不同的声音。每种声音都有其音量和音调的特征。一系列声音称为音乐。音乐被考虑 美丽 如果任何两个连续的声音仅在音量或仅在音高上不同。音乐被考虑 无聊 如果任意三个连续声音的音量或音高相同。

你想要作曲 美丽, 非-无聊 音乐,其中包含您的乐器产生的每种声音一次。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

在每个测试用例的第一行,有一个数字 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 乐器可以发出的声音数量。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 行包含一对数字 $$$v_i, p_i$$$ ($$$1 \le v_i,\space p_i \le 10^9$$$) — 分别是第 $$$i$$$ 声音的音量和音高。保证所有 $$$n$$$ 声音中没有重复项,这意味着对于任何 $$$i \neq j$$$,至少满足 $$$v_i \neq v_j$$$ 或 $$$p_i \neq p_j$$$ 条件之一。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以创作这样的音乐,则输出“是”,并在下一行输出 $$$n$$$ 数字 — 按形成优美而不无聊音乐的顺序排列的声音索引。否则,输出“NO".

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“是", "是", "是“,和”是”将被接受为肯定答案。

示例

输入
复制

5
4
179 239
179 179
239 179
239 239
3
1 1
2 1
3 1
1
5 7
5
1 1
1 2
2 1
2 2
99 99
7
1 1
1 3
2 1
2 2
3 1
3 2
3 3

输出
复制

YES
4 3 2 1 
NO
YES
1 
NO
YES
3 4 6 7 2 1 5 

注意

在第一个测试用例中,音乐 $$$(239,239)-(239,179)-(179,179)-(179,239)$$$ 是合适的,包含所有声音,并且所有连续的声音仅在音量上或仅在音高上不同。

在第二个测试用例中,可以表明没有适合给定声音的音乐。