未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖)，每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ..., xn，请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，第一行是整数N(2 < N < 10)，第二行是N个整数，x1, x2,..., xn(0 ≤ xi ≤ N)。

Output

对输入的每组测试数据，如果不存在可能的相连关系，输出"NO"。否则输出"YES"，并用N×N的矩阵表示湖泊间的相邻关系，即如果湖泊i与湖泊j之间有水路相连，则第i行的第j个数字为1，否则为0。每两个数字之间输出一个空格。如果存在多种可能，只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

Sample Input

3
7
4 3 1 5 4 2 1 
6
4 3 1 4 2 0 
6
2 3 1 1 2 1

Sample Output

YES
0 1 0 1 1 0 1 
1 0 0 1 1 0 0 
0 0 0 1 0 0 0 
1 1 1 0 1 1 0 
1 1 0 1 0 1 0 
0 0 0 1 1 0 0 
1 0 0 0 0 0 0 

NO

YES
0 1 0 0 1 0 
1 0 0 1 1 0 
0 0 0 0 0 1 
0 1 0 0 0 0 
1 1 0 0 0 0 
0 0 1 0 0 0

题意：

       给出每个青蛙的邻居的个数，判断是否存在相连关系。

思路：

      判断是否可以构成图。

      给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此一一对应，则称此序列可图化。判断一个序列是否可图化，用Havel-Hakimi定理（握手定理）判断。

   （1）先从小到大排序

   （2)  删去最后一个数字，并且把对后一个数字对应个数的元素减一

   （3）继续排序，进行上述操作，直至所有元素都为0，就表明序列可图化，如果出现元素为负或者大于元素个数就可以判断为不能构成图。

举例：

序列：4  3  1  5  4  2  1
排序之后：1  1  2  3  4  4  5
删除5对前面5个数减1操作
1 0 1 2 3 3
排序
0 1 1 2 3 3
删除3对前面3个数减1操作
0 1 0 1 2
排序
0 0 1 1 2
删除2 对前面2个数减1操作
0 0 0 0
全为0，可图

 

写完发现答案跟样例答案不一样但是，才发现是special judge！

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct data
{
	int h;
	int mark;
};
int cmp(data x,data y)
{
	return x.h<y.h;
}
int main()
{
	int n,t,i,flag,m,j;
	data a[25]; 
	int map[25][25];
	scanf("%d",&t);
	while(t--)
	{
		memset(map,0,sizeof(map));
		flag=0;
		scanf("%d",&n);
		m=n;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i].h);
			a[i].mark=i;
		}
		while(n)
		{
			sort(a,a+n,cmp);
			if(a[n-1].h<0||a[n-1].h>=n) 
			{
				flag=1;
				break;
			}
			for(i=n-2;i>n-2-a[n-1].h;i--)
			{
				map[a[n-1].mark][a[i].mark]=map[a[i].mark][a[n-1].mark] = 1;
				a[i].h--;
			}
			n--;
		}
		if(flag==1)
			printf("NO\n");
		else
		{
			printf("YES\n");
			for(i=0;i<m;i++)
			{
				for(j=0;j<m;j++)
				{
					printf("%d ",map[i][j]);
				}
				printf("\n");
			}	
		}
		printf("\n");
	 } 
	 return 0;
}