← 返回题目列表

Codeforces · 23/C

C. 橙子和苹果

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

2N - 1 个盒子里有苹果和橙子。你的任务是选择 N 个盒子,其中包含不少于一半的苹果和不少于一半的橙子。

输入

第一个输入行包含一个数字 T — 测试数量。每个测试的描述都以自然数 N 开始——盒子的数量。以下 2N - 1 行中的每一行都包含数字 ai 和 oi — 第 i 个盒子中苹果和橙子的数量 (0 ≤ ai, oi ≤ 109)。输入中所有测试中的N之和不超过105。所有输入数字均为整数。

输出

每个测试输出两行。在第一行中,如果可以选择N个框,则输出YES,否则输出NO。如果答案是肯定的,则在第二行输出 N 个数字 — 所选框的索引。框按照输入顺序从 1 开始编号。否则将第二行留空。数字之间用一个空格分隔。

示例

输入 #1

2
2
10 15
5 7
20 18
1
0 0

输出 #1

YES
1 3
YES
1