D. Districts Connection

D. Districts Connection

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There are nn districts in the town, the ii-th district belongs to the aiai-th bandit gang. Initially, no districts are connected to each other.

You are the mayor of the city and want to build n−1n−1 two-way roads to connect all districts (two districts can be connected directly or through other connected districts).

If two districts belonging to the same gang are connected directly with a road, this gang will revolt.

You don't want this so your task is to build n−1n−1 two-way roads in such a way that all districts are reachable from each other (possibly, using intermediate districts) and each pair of directly connected districts belong to different gangs, or determine that it is impossible to build n−1n−1 roads to satisfy all the conditions.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤5001≤t≤500) — the number of test cases. Then tt test cases follow.

The first line of the test case contains one integer nn (2≤n≤50002≤n≤5000) — the number of districts. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the gang the ii-th district belongs to.

It is guaranteed that the sum of nn does not exceed 50005000 (∑n≤5000∑n≤5000).

Output

For each test case, print:

• NO on the only line if it is impossible to connect all districts satisfying the conditions from the problem statement.
• YES on the first line and n−1n−1 roads on the next n−1n−1 lines. Each road should be presented as a pair of integers xixi and yiyi (1≤xi,yi≤n;xi≠yi1≤xi,yi≤n;xi≠yi), where xixi and yiyi are two districts the ii-th road connects.

For each road ii, the condition a[xi]≠a[yi]a[xi]≠a[yi] should be satisfied. Also, all districts should be reachable from each other (possibly, using intermediate districts).

Example

input

Copy

4
5
1 2 2 1 3
3
1 1 1
4
1 1000 101 1000
4
1 2 3 4

output

Copy

YES
1 3
3 5
5 4
1 2
NO
YES
1 2
2 3
3 4
YES
1 2
1 3
1 4

=========================================================================

可以说CF上ABCD里面遇见的所谓图论树连边问题，都是抓住一个点进行连接。本题要求不能把相同的连接到一起。那么我们就选两个不同的点，a,b 把b全部连到a,再把剩下的b之外的全部连到b

#include
# include
using namespace std;
typedef long long int  ll;
 
int a[5010];
bool book[5010];
 
 
int main ()
{
 
     int t;
     cin>>t;
 
     while(t--)
     {
         int n;
 
         cin>>n;
 
      for(int i=1;i<=n;i++)
      {
          book[i]=0;
      }
 
         int root1=0,root2=0;
         int pos1,pos2;
         for(int i=1;i<=n;i++)
         {
             cin>>a[i];
 
             if(!root1)
             {
                 root1=a[i];
                 pos1=i;
             }
             else if(root1&&a[i]!=root1)
             {
                 root2=a[i];
                 pos2=i;
             }
         }
 
         if(root2==0)
         {
             cout<<"NO"<
         }
         else
         {
             cout<<"YES"<
 
             for(int i=1;i<=n;i++)
             {
                 if(a[i]==root2)
                 {
                     cout<" "<
                     book[i]=1;
                 }
             }
 
             for(int i=1;i<=n;i++)
             {
                 if(i!=pos1&&!book[i])
                 {
                     cout<" "<
                 }
             }
         }
 
 
 
 
     }
 
    return 0;
 
}