Плоска організація

Компанія, в якій ви працюєте, вирішила максимально спростити організаційну структуру: для кожної пари співробітників **A** і **B** або **A** є безпосереднім керівником **B**, або **B** є безпосереднім керівником **A**. Це означає, що тепер у кожного співробітника може бути багато безпосередніх начальників. І це чудово, адже це змушує співробітника відчувати, що його робота важлива для багатьох людей, а не лише для одного менеджера — так кажуть керівники.

Однак завжди є можливість для вдосконалення. Як корпоративна мета на цей рік, ієрархія буде переглянута, щоб гарантувати, що кожного разу, коли людина **A** безпосередньо контролюється людиною **B**, **B** водночас опосередковано контролюється **A**. Ми кажемо, що **B** опосередковано контролюється **A**, якщо існує **n** > **2** і така послідовність (`c[1]`, ... `c[n]`), що `c[1]` = **A**, `c[n]` = **B** і для кожного **i** < **n**, `c[i]` є безпосереднім керівником `c[i+1]`).

За словами керівників, це гарантує, що будь-який співробітник двічі подумає, перш ніж зловживати своєю владою над кимось іншим.

Не дивно, що хтось може розсердитися, якщо дізнається, що його підлеглий раптово став його начальником. І деякі такі рішення можуть викликати більше обурення, ніж інші. Ваше завдання — виконати корпоративну мету, змінивши деякі залежності між співробітниками так, щоб сума образ від цих змін була якомога меншою.

#### Вхідні дані
Перший рядок містить кількість тестів **z** (**1** ≤ **z** ≤ **100**). Далі йдуть описи тестів.

Перший рядок кожного набору вхідних даних містить одне ціле число **n** (**1** ≤ **n** ≤ **2000**) — кількість співробітників. Співробітники пронумеровані від **1** до **n**.

Потім слідують **n** рядків, кожен з яких містить **n** цілих чисел `d[i,j]` (**0** ≤ `d[i,j]` ≤ **2** * `10^9`). Якщо співробітник **i** є безпосереднім керівником співробітника **j**, то `d[i,j]` > **0** описує образу, яку **i** відчув би, якби ця залежність була змінена. В іншому випадку (тобто, якщо **j** є безпосереднім керівником **i** або якщо **i** = **j**), то `d[i,j]` = **0**.

Загальна кількість співробітників у всіх тестах не перевищує **10000**.

#### Вихідні дані
Для кожного тесту знайдіть рішення, яке гарантує, що для будь-якої пари співробітників **i**, **j** (**1** ≤ **i**, **j** ≤ **n**, **i** ≠ **j**), або **i** буде безпосереднім керівником **j**, або **j** буде опосередкованим керівником **i**, або навпаки. Ваше рішення повинно звести до мінімуму суму невдоволення співробітників. Якщо існує більше одного такого рішення, ви можете вивести будь-яке з них.

Якщо рішення не існує, виведіть слово **"NO"**.

В іншому випадку в першому рядку виведіть слово **"YES"**. У другому рядку виведіть два цілі числа **k** і **r** — кількість залежностей між співробітниками, які ви збираєтеся змінити, і досягнута сума образ відповідно. Зверніть увагу, що вам не потрібно мінімізувати **k**.

Потім виведіть **k** рядків, по два цілі числа в кожному — ідентифікатори співробітників **a**, **b** (**1** ≤ **a**, **b** ≤ **n**, **a** ≠ **b**), так що **a** в даний час є безпосереднім керівником **b**, і їхні відносини повинні змінитися на протилежні. Не слід виводити одну і ту ж пару співробітників більше одного разу.