Problem: 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 ai and oi — amount of apples and oranges in the i-th box (0 ≤ ai, oi ≤ 109). The sum of N in all the tests in the input doesn't exceed 105. 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

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
  public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 1000000007;
    long fac[]= new long[1000001];
    long inv[]=new long[1000001];
    public  void solve() throws IOException 
    {
 
        //int t = readInt();
          int t = readInt();
          for(int f =0;f<t;f++){
           int n = readInt();
 
             n=2*n-1;
           int a[]=new int [n+1];
 
           
 
           int b[]=new int[n+1];
 
 
           for(int i =0;i<n;i++){
            a[i]= readInt();
            b[i]= readInt();
            }
 
 
 
           ArrayList<edge> e = new ArrayList<edge>();
 
           ArrayList<edge> e1 = new ArrayList<edge>();
 
 
 
 
           
           PriorityQueue<edge>  hea = new PriorityQueue<edge>();
 
           PriorityQueue<edge>  heb = new PriorityQueue<edge>();
 
 
 
 
 
           for(int i =0;i<n;i++)
           {
 
 
               e.add(new edge(b[i],a[i],i));
 
               e1.add(new edge(a[i],b[i],i));
 
           }
 
           Collections.sort(e);
 
           Collections.sort(e1);
           int reva[]=new int[n+1];
           int revb[]=new int[n+1];
           int no =n;
           for(int i =0;i<n;i++)
           {
              int ind= e.get(i).ind ;
              a[ind+1]= no;
              reva[no]=ind+1;
              no--;
           }
 
 
           no =n;
 
 
           for(int i =0;i<n;i++)
           {
              int ind = e1.get(i).ind;
              revb[no]= ind+1;
              b[ind+1]=no;
              no--;
           }
 
 
           int starta =1;
 
           int startb =1;
 
           boolean check[]=new boolean[n+1];
 
           //boolean checkb[]=new boolean[n+1];
 
 
           int counta=0;
           int countb=0;
 
 
           int moves = n/2+1;
   
           ArrayList<Integer> res = new ArrayList<Integer>();
 
           for(int i =0;i<moves ;i++)
           {
 
              if(i%2==0)
              {
                   while(starta<=n)
                   {
                     int tara = n-starta+1;
                     //System.out.println(reva[tara]+" "+tara);
                     if(check[reva[tara]])
                     {
                       counta++;
                     }
                     else
                     { 
                        hea.add(new edge(0,b[reva[tara]],reva[tara]));
                       // check[rev[tara]]= true;
                     }
                    
                     if(counta<(starta+1)/2)
                     {
                       break;
                     }
 
                     starta++;
 
                  }
                  while(true)
                  {
                    if(hea.size()==0)
                        break;
                     edge kl = hea.poll();
                     
                     int yo = kl.v;
                     
                     int ind = kl.ind;
 
                     if(!check[ind])
                     {
                        res.add(ind);
                       check[ind]= true;
                       int go= n-b[ind]+1;
                       counta++;
                       starta++;
                       if(go<startb)
                       {
                           countb++;
                       }
                       break;   
                     }
                    
 
                  }
              }
              else
              {
                   while(startb<=n)
                   {
 
                      int tarb  = n-startb+1;
                      if(check[revb[tarb]])
                      {
                         countb++;
                      }
                      else
                      {
                         heb.add(new edge(0,a[revb[tarb]],revb[tarb]));
                      }
                      if(countb<(1+startb)/2)
                      {
                         break;               
                      }
 
                      startb++;
 
                   }
 
                  while(true)
                  {
                    if(heb.size()==0)
                        break;
                     edge kl = heb.poll();
                     
                     int yo = kl.v;
                     
                     int ind = kl.ind;
 
                     if(!check[ind])
                     {
                       res.add(ind);
                       check[ind]= true;
                       int go= n-a[ind]+1;
                       countb++;
                       startb++;
                       if(go<starta)
                       {
                           counta++;
                       }   
                       break;
                     }
                     
 
                  }
 
 
 
 
 
              }
           }
 
 
           out.println("YES");
 
 
           for(int i =0;i<res.size();i++)
            out.print(res.get(i)+" ");
 
           out.println();
 
 
 
 
          }
 
 
       
    }
 
 
    int modInverse(int a, int m)
    {
        int m0 = m;
        int y = 0, x = 1;
 
        if (m == 1)
            return 0;
 
        while (a > 1) {
            // q is quotient
            int q = a / m;
 
            int t = m;
 
            // m is remainder now, process
            // same as Euclid's algo
            m = a % m;
            a = t;
            t = y;
 
            // Update x and y
            y = x - q * y;
            x = t;
        }
 
        // Make x positive
        if (x < 0)
            x += m0;
 
        return x;
    }
 
    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);
 
    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int u ;
    int v;
    int ind;
    
    edge(int u, int v, int ind )
    {
       this.u=u;
       this.v=v;
       this.ind= ind;
    }
    public int compareTo(edge e)
    {
        if(this.v!=e.v)
        return -this.v+e.v;
 
        return -this.u+e.u;
    }
}