cf23C. Oranges and Apples

In 2N - 1 boxes there are apples and oranges. Your task is to choose N boxes so, that they will contain not less than half of all the apples and not less than half of all the oranges.

Input

The first input line contains one number T — amount of tests. The description of each test starts with a natural number N — amount of boxes. Each of the following 2N - 1 lines contains numbers a_i and o_i — amount of apples and oranges in the i-th box (0 ≤ a_i, o_i ≤ 10⁹). The sum of N in all the tests in the input doesn't exceed 10⁵. All the input numbers are integer.

Output

For each test output two lines. In the first line output YES, if it's possible to choose N boxes, or NO otherwise. If the answer is positive output in the second line N numbers — indexes of the chosen boxes. Boxes are numbered from 1 in the input order. Otherwise leave the second line empty. Separate the numbers with one space.

Examples

Input

2
2
10 15
5 7
20 18
1
0 0

Output

YES
1 3
YES
1
思路：详细思路可以看这个题解
https://blog.csdn.net/Yunyouxi/article/details/23964903?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.edu_weight&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.edu_weight

唯一需要补充的地方就是，这个题肯定有解的，不会存在输出NO的情况，因为在划分成为一半的情况下，肯定有一方大于另一方，也就是有一边是大于总合的一半的，所以上面题解输出NO的情况可以省略

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
struct node{
    int x,y,ans;
}a[N];
bool cmp(node t1,node t2) {
    return t1.x<t2.x;
}
int main()
{
    int t;
    cin>>t;
    while(t--) {
        int n;
        ll sumx = 0;
        ll sumy = 0;
        cin>>n;
        for(int i = 1; i<=2*n-1; i++) {
            cin>>a[i].x>>a[i].y;
            sumx += a[i].x;
            sumy += a[i].y;
            a[i].ans = i;
        }
        sort(a+1,a+(2*n-1)+1,cmp);
        ll sum1 = 0;
        ll sum2 = 0;
        for(int i = 1; i <= 2*n-1; i++) {
            if(i%2 != 0) {
                sum1 += a[i].y;
            }
            else {
                sum2 += a[i].y;
            }
        }
        if(sum1*2 > sumy) {
            cout<<"YES"<<endl;
            for(int i = 1; i <= 2*n -1; i++) {
                if(i%2 != 0)
                    cout<<a[i].ans<<" ";
            }
            cout<<endl;
        }
        else{
            cout<<"YES"<<endl;
            for(int i = 1; i <= 2*n-1; i++) {
                if(i % 2 == 0)
                    cout<<a[i].ans<<" ";
            }
            cout<<a[2*n-1].ans<<endl;
        }
    }
    return 0;
}