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

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

3 секунди

128 мегабайтів

Складна

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

Однак завжди є можливість для вдосконалення. Як корпоративна мета на цей рік, ієрархія буде переглянута, щоб гарантувати, що кожного разу, коли людина $A$ безпосередньо контролюється людиною $B$ , $B$ водночас опосередковано контролюється $A$ . Ми кажемо, що $B$ опосередковано контролюється $A$ , якщо існує $n > 2$ n > 2 і така послідовність $c_{1}, \dots, c_{n}$ c_1, \ldots, c_n, що $c_{1} = A$ c_1 = A, $c_{n} = B$ c_n = B і для кожного $i < n$ i < n, $c_{i}$ c_i є безпосереднім керівником $c_{i + 1}$ c_{i+1}.

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

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

Вхідні дані

Перший рядок містить кількість тестів $z$ ( $1 \leq z \leq 100$ 1 \le z \le 100). Далі йдуть описи тестів.

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

Потім слідують $n$ рядків, кожен з яких містить $n$ цілих чисел $d_{i, j}$ d_{i,j} ( $0 \leq d_{i, j} \leq 2 \cdot 1 0^{9}$ 0 \le d_{i,j} \le 2 \cdot 10^9). Якщо співробітник $i$ є безпосереднім керівником співробітника $j$ , то $d_{i, j} > 0$ d_{i,j} > 0 описує образу, яку $i$ відчув би, якби ця залежність була змінена. В іншому випадку (тобто, якщо $j$ є безпосереднім керівником $i$ або якщо $i = j$ i = j), то $d_{i, j} = 0$ d_{i,j} = 0.

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

Вихідні дані

Для кожного тесту знайдіть рішення, яке гарантує, що для будь-якої пари співробітників $i$ , $j$ ( $1 \leq i, j \leq n$ 1 \le i, j \le n, $i \neq = j$ i \ne j), або $i$ буде безпосереднім керівником $j$ і $j$ буде опосередкованим керівником $i$ , або навпаки. Ваше рішення повинно звести до мінімуму суму невдоволення співробітників. Якщо існує більше одного такого рішення, ви можете вивести будь-яке з них.

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

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

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

Приклади

Приклад 1