10/04/2025 22:30:07

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2412. Сортировка

Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Задан набор из

$M$ операций обмена

$(a_1,b_1),\ …,\ (a_M,\ b_M)$ над массивом из

$N$ чисел

$X_1,\ …,\ X_N$ . Необходимо отсортировать массив в неубывающем порядке, используя эти операции обмена. Каждая пара

$(a_i,\ b_i)$ означает, что можно поменять местами элементы массива

$X_{a_i}$ и

$X_{b_i}$ . Операции обмена можно применять неограниченное количество раз и в произвольном порядке.

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

Первая строка ввода содержит два целых числа – размер массива

$N$ (

$2\ ≤\ N\ ≤\ 100000$ ) и количество операций обмена

$M$ (

$1\ ≤\ M\ ≤\ min(200000,(N*(N-1))/2)$ ). Далее следует

$M$ строк, содержащих по два целых числа

$a_i,\ b_i$ (

$1\ ≤\ a_i\ <\ b_i\ ≤\ N$ ) – описание операции обмена. Далее следует строка, содержащая одно целое число

$K$ (

$1\ ≤\ K\ ≤\ 10$ ) – количество массивов, которые нужно отсортировать. Далее следует

$K$ строк, в каждой строке по

$N$ целых чисел в диапазоне от 0 до

$10^9$ - массивы для сортировки.

Вывести

$K$ строк, для каждого массива вывести на соответствующей строке сообщение YES, если массив можно отсортировать с помощью заданного набора операций обмена, иначе вывести сообщение NO.

Пример ввода

Пример вывода

YES
NO