Есть n контейнеров и какое-то количество шаров разного цвета, количество разных цветов тоже n. Шары в случайном порядке распределены по контейнерам. Допустима лишь одна операция с шарами: два шара в разных контейнерах можно поменять местами. Нужно ответить на вопрос: можно ли используя эту единственную операцию отсортировать шары так, чтобы выполнялись такие условия:
- в каждом контейнере лежат лишь шары одинакового цвета
- каждый цвет лежит лишь в одном контейнере
1<= n <= 100 - количество контейнеров и цветов 0 <= количество шаров одного цвета в одном контейнере <= 1000000000
Первая строчка содержит n. Остальные n строчек содержат n чисел, разделённых пробелами. Каждая строчка описывает содержимое контейнера. Каждое из чисел обозначает количество шаров i-го цвета в этом контейнере, где i - порядковый номер числа в строчке.
Написать "yes", если сортировку можно сделать, или "no", если нельзя.
Пример 1:
Вход:
2
1 2
2 1
Выход: yes
Пояснение: у нас две коробки с (условно) красными и зелёными шарами. В первой коробке один красный и два зелёных, во второй - два красных и один зелёный. Если из первой коробки взять красный шар, из второй - зелёный и поменять их местами (допустимая операция), то мы получаем, что в первой коробке три зелёных шара и других нет, а во второй - три красных шара и других тоже нет. То есть получилось выполнить нужную сортировку.
Пример 2:
Вход:
3
10 20 30
1 1 1
0 0 1
Выход: no
Пояснение: у нас три коробки и три цвета, условно красный, зелёный и синий. В первой коробке 10 красных, 20 зелёных и 30 синих. Во второй - по одному шару каждого цвета. В третьей - лишь один синий шар. Как шары местами не меняй, но в первой коробке всегда будут все три цвета, то есть сделать сортировку не получается.