L'entreprise pour laquelle vous travaillez actuellement a décidé de pousser l'idée d'une structure organisationnelle plate à ses limites : pour chaque paire d'employés $A$ et $B$, soit $A$ a été désigné pour superviser directement le travail de $B$, soit $B$ a été désigné pour superviser directement le travail de $A$. Bien sûr, cela signifie que l'on peut désormais avoir un grand nombre de superviseurs directs... ce qui est formidable, car cela permet à un employé de sentir que son travail est vraiment important pour tant de personnes plutôt que pour un seul manager, disent les cadres.

Cependant, il y a toujours place à l'amélioration. Comme objectif d'entreprise pour cette année, la hiérarchie sera révisée pour garantir que chaque fois qu'une personne $A$ est directement supervisée par une personne $B$, alors $A$ est également indirectement supervisée par $B$ en même temps (nous disons que $A$ est indirectement supervisée par $B$ s'il existe $n > 2$ et une séquence $(c_1, \dots, c_n)$ telle que $c_1 = B$, $c_n = A$ et pour chaque $i < n$, $c_i$ est un superviseur direct de $c_{i+1}$).

Cela garantira que tout employé réfléchira à deux fois avant de décider d'abuser de sa position de pouvoir sur quiconque, disent les cadres.

Il ne devrait pas être surprenant, cependant, que l'on puisse être quelque peu contrarié d'apprendre que son subordonné a soudainement été nommé comme son superviseur. Et certaines de ces décisions peuvent causer plus de ressentiment que d'autres. Votre tâche est d'atteindre l'objectif de l'entreprise en inversant certaines des dépendances entre les employés de telle sorte que la somme des ressentiments liés à ces changements soit aussi faible que possible.

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 100$). Les descriptions des cas de test suivent.

La première ligne de chaque cas de test contient un entier unique $n$ ($1 \le n \le 2000$) – le nombre d'employés. Les employés sont numérotés de $1$ à $n$.

Suivent $n$ lignes, contenant $n$ entiers $d_{i,j}$ chacun ($0 \le d_{i,j} \le 2 \cdot 10^9$). Si l'employé $i$ est un superviseur direct de l'employé $j$, alors $d_{i,j} > 0$ décrit le ressentiment que $i$ ressentirait si cette dépendance était inversée. Sinon (c'est-à-dire, si $j$ est un superviseur direct de $i$ ou si $i = j$), $d_{i,j} = 0$.

Le nombre total d'employés dans tous les cas de test ne dépasse pas $10000$.

Sortie

Pour chaque cas de test, produisez une solution qui garantit que, pour toute paire d'employés $i, j$ ($1 \le i, j \le n, i \neq j$), soit $i$ sera un superviseur direct de $j$ et $j$ sera un superviseur indirect de $i$, ou vice versa. Votre solution doit minimiser la somme des ressentiments que les employés ressentiront. Si plus d'une telle solution existe, vous pouvez en imprimer n'importe laquelle.

Si aucune solution n'existe, vous devez afficher une seule ligne contenant le mot « NO ».

Sinon, dans la première ligne, affichez un seul mot « YES ». Dans la deuxième ligne, imprimez deux entiers $k$ et $r$ – le nombre de dépendances entre les employés que vous avez l'intention d'inverser et la somme de ressentiment atteinte, respectivement. Notez que vous n'avez pas besoin de minimiser $k$.

Ensuite, affichez $k$ lignes, chacune contenant deux entiers – les identifiants des employés $a, b$ ($1 \le a, b \le n, a \neq b$) tels que $a$ est actuellement un superviseur direct de $b$ et leur relation doit être inversée. Vous ne devez jamais afficher la même paire d'employés plus d'une fois.

Exemples

Entrée 1

1
5
0 1 0 6 11
0 0 1 6 12
2 0 0 7 12
0 0 0 0 4
0 0 0 0 0

Sortie 1

YES
2 10
4 5
2 4