Порядок Фаркуада#12977

Порядок Фаркуада

2 секунди
512 мегабайтів
Дуже складна

Лорд Фаркуад має таблицю , що складається з цілих чисел та має рядків та стовпців. Оскільки він є одержимий порядком, він хоче щоб кожен рядок таблиці був впорядкований у неспадному порядку.

Шрек не поділяє такої жаги Фаркуада до порядку, тому має інший план. Шрек може переставляти числа у стовпці у довільному порядку і хоче зробити так, щоб жоден рядок у таблиці не був у неспадному порядку. Чи зможе він досягнути своєї цілі?

Масив a_1, a_2, \ldots, a_k називають неспадним, якщо a_1 \leq a_2 \leq \ldots \leq a_k.

Вхідні дані

Вам потрібно опрацювати декілька тестів. У першому рядку задано одне ціле число — кількість тестів.

У першому рядку кожного тесту задано два цілі числа — розміри таблиці.

Після цього у кожному тесті задано рядів. У -тому рядку задано цілих чисел a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} — елеметни -того рядка.

1 \leq t\leq 2\cdot 10^4,

2 \leq n, m \leq 10^5,

n\cdot m \leq 2\cdot 10^5,

Сума n\cdot m по всіх тестах не перевищує 2\cdot 10^5,

1 \leq a_{i, j} \leq 10^9.

Вихідні дані

Для кожного тесту виведіть відповідь. Якщо Шрек може зробити кожен рядок не неспадним, виведіть YES. В іншому випадку виведіть NO.

Приклади

Приклад

Loading
Loading

Примітка

У першому тесті, перший рядок спочатку виглядає так: , отже він є неспадним. Проте, Шрек може змінювати елементи першого стовпця і отримати:

2024

69

69

42

У другому прикладі, неможливо зробити всі рядки не неспадними.

У третьому прикладі, Шрек може переставити елементи так:

1

1

2

1

1

2

1

1

2

1

1

2