题目描述

徐老师所在的城市里的路口非常多，导致道路非常混乱，所以市政府准备进行一次道路规划，使得城市道路变得简洁清晰。

市政府希望将整个城市的道路规划成一棵树，也就是说如果城市共有 $n$ 个路口，那么最后只留下 $n-1$ 条双向道路使得所有路口都连通。

同时，市政府认为对于一个路口 $i$ 来说，所有和它直接相连的道路长度的平均值，就是这个路口的视野好坏程度，市政府会选择视野最好的路口作为中心路口

为了加快规划进度，市政府向所有市民征集规划方案，徐老师自然也想为城市建设处一份力，于是他仔仔细细的走遍了城市的每一条道路，列出了所有信息。

徐老师每次会给出一个规划方案，这个方案是一张 $n$ 行 $n$ 列的表格 $A$。

其中 $A_{i,j}$ 表示徐老师的规划中第 $i$ 个路口到第 $j$ 个路口的最短距离为 $A_{i,j}$

当然这 $A_{i,j}$ 只是表示第 $i$ 个路口到第 $j$ 个路口的最短距离为 $A_{i,j}$，并不一定表示第 $i$ 个路口和第 $j$ 个路口一定存在一条双向道路连接。

徐老师列出了好多种他想到的规划方案，但是他不确定这些方案是否正确。

现在他希望你来帮他判断一下，某个方案是否足够正确，如果正确则请你再告诉他中心路口是哪个路口，如果存在多个视野程度一样的路口，则选择编号小的路口作为中心路口。

输入格式

输入第一行包含一个正整数 $T$ 表示共有 $T$ 组测试数据 对于每组测试数据： 第一行包含一个正整数 $n$ 接下来 $n$ 行每行包含 $n$ 个整数表示道路长度

输出格式

对于每组测试数据，如果规划方案是清晰的，则输出 Yes 否则输出 No 如果规划方案是清晰的，则再输出中心路口的编号。

Samples

3
3
0 5 9
5 0 4
9 4 0
3
1 2 3
1 0 3
1 2 0
3
0 0 9
5 0 4
9 0 0

Yes
1
No
No

数据范围

对于 $30\%$ 的数据，$n \leq 50$

对于 $50\%$ 的数据，$n \leq 600$

对于 $100\%$ 的数据，$n \leq 2500$

对于所有数据保证 $T \leq 5, 0 \leq A_{i,j} \leq 10^9$

样例解释

对于第一组样例可以发现，城市中的道路为 $1-2$ 存在一条长度为 $5$ 的双向道路，$2-3$ 存在一条长度为 $4$ 的双向道路，$1-3$ 的最短距离为 $9$，那么这个规划就是正确的 其中视野最好的路口是 $1$

对于第二组样例，$1-1$ 存在自环，所以不满足条件