시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 0 | 0 | 0 | 0.000% |
В компании «Почтальон Печкин и Ко» работает n сотрудников. Зарплата каждого сотрудника этой компании состоит из двух частей: оклада и бонуса. Так, i-й сотрудник каждый месяц получает xi рублей оклада и yi рублей бонуса.
Руководству компании стало известно, что ее сотрудники стали обмениваться информацией о своих зарплатах. Руководство выяснило, что существует m таких пар сотрудников ui и vi, что сотрудник ui регулярно сообщает сотруднику vi свою зарплату. В качестве наказания за нарушение корпоративного этикета, руководство компании хочет максимально расстроить своих сотрудников. Руководство считает, что цель достигнута, если для каждой пары сотрудников u и v, таких что u сообщает свою зарплату v, выполняется хотя бы одно из двух следующих условий:
В процессе достижения этого требования руководство не хочет вносить существенные изменения в зарплатную политику компании. Поэтому единственное, что готово сделать руководство — выбрать несколько сотрудников и каждому из них поменять местами сумму его бонуса и сумму его оклада. Чтобы минимизировать бухгалтерскую отчетность от этой операции, число сотрудников, у которых будут меняться местами оклад и бонус должно быть минимально.
Руководство компании обратилось к вам с просьбой выяснить, может ли их цель быть достигнута таким методом. В случае же, если цель может быть достигнута, вам необходимо также выяснить, у каких именно сотрудников необходимо поменять местами оклад и бонус.
Первая строка содержит одно целое число T — количество тестовых примеров, которые необходимо обработать. Далее следует описание самих случаев.
Первая строка описания каждого тестовго примера содержит два целых числа n и m — количество сотрудников в компании и количество пар сотрудников, которых руководство уличило в обмене информацией. Следующие n строк содержат по два целых числа xi и yi (1 ≤ xi, yi ≤ 109) — оклад и бонус соответствующего сотрудника.
Следующие m строк содержат по два целых числа ui и vi (1 ≤ ui ≠ vi ≤ n). Каждая такая строка означает, что сотрудник ui сообщает свою зарплату сотруднику vi.
Гарантируется, что сумма n во всех тестовых примерах и сумма m во всех тестовых примерах не превосходят 105.
Для каждого тестового примера в отдельной строке выведите -1, если требования руководства невыполнимы. Если же они выполнимы, выведите число k — минимальное количество сотрудников, которым необходимо поменять местами суммы оклада и бонуса, а затем k различных чисел, разделенных пробелами — номера этих сотрудников. В случае, если оптимальных ответов несколько, выведите любой.
2 3 3 2 2 1 1 3 3 2 1 3 2 1 3 3 2 1 2 2 3 3 4 2 1 3 2
-1 0
1 3 2 1 2 1 2 3 4 2 1 3 2
1 2
Contest > Russian Code Cup > 2014 > RCC 2014 Elimination Round E번