Знакомства в лагере «Кыргызчыл»
В летнем лагере «Кыргызчыл» на Иссык-Куле вожатые составили отчёт: для каждого из n школьников записали, со сколькими другими школьниками он познакомился за смену, — это числа d[1], …, d[n]. Знакомства взаимные, с самим собой знакомиться нельзя, а два школьника либо знакомы, либо нет.
Директор подозревает ошибку в отчёте. Для каждого отчёта ответьте на два вопроса:
- может ли вообще быть, что школьник
iзнаком ровно сd[i]другими (для всехiсразу)? - может ли при этом ещё и оказаться, что через цепочки знакомств связаны все школьники (любые двое — знакомые, знакомые знакомых и так далее)?
Входные данные
В первой строке — число T (1 ≤ T ≤ 10⁴) — количество отчётов. Каждый отчёт задан двумя строками: в первой — n (1 ≤ n ≤ 2 · 10⁵), во второй — n чисел d[i] (0 ≤ d[i] ≤ n − 1). Сумма всех n не превосходит 2 · 10⁵.
Выходные данные
Для каждого отчёта выведите в отдельной строке два слова YES или NO — ответы на первый и второй вопросы.
Пример 1
Вход:
4
4
3 3 1 1
4
1 1 1 1
4
2 2 2 2
1
0
Выход:
NO NO
YES NO
YES YES
YES YES
Пояснение
Отчёт 3 3 1 1 невозможен: двое школьников знакомы со всеми тремя остальными, а значит, и у каждого из двух других хотя бы два знакомства. Отчёт 1 1 1 1 возможен (две пары знакомых), но тогда школьники не связаны в одну компанию. Отчёт 2 2 2 2 — это четыре школьника по кругу.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов n ≤ 6.
Подсказка
Теорема Эрдёша — Галлаи: невозрастающая последовательность d[1] ≥ … ≥ d[n] с чётной суммой реализуема простым графом тогда и только тогда, когда для каждого k выполнено d[1] + … + d[k] ≤ k(k − 1) + Σ_{i > k} min(d[i], k).
Комментарии