Олимпиадный тренинг

Задача . C. Зависть


Задача

Темы: графы снм Структуры данных *2300

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

Вам дан граф G. Если вы запустите алгоритм по поиску минимального остовного дерева, вы найдете лишь одно минимальное остовное дерево, а другие ребра будут завидовать. Вам дано несколько запросов, каждый запрос содержит подмножество ребер графа G, определите, существует ли минимальное остовное дерево этого графа, содержащее все эти ребра, или нет.

Входные данные

Первая строка содержит два целых числа n, m (2  ≤ n, m  ≤ 5·105, n - 1 ≤ m) — количество вершин и ребер в графе, соответственно.

i-я из следующих m строк содержит три целых числа ui, vi, wi (ui ≠ vi, 1 ≤ wi ≤ 5·105) — концы и вес i-го ребра. Возможно, что существует более одного ребра между некоторыми парами вершин. Гарантируется, что данный граф связен.

Следующая строка содержит одно целое число q (1 ≤ q ≤ 5·105) — количество запросов.

Далее следуют q строк, i-я из них содержит описание i-го запроса. Она начинается с целого числа ki (1 ≤ ki ≤ n - 1) — размера подмножества ребер, а затем следуют ki различных целых чисел от 1 до m — индексы ребер в подмножестве. Гарантируется, что сумма значений ki для всех 1 ≤ i ≤ q не превосходит 5·105.

Выходные данные

Для каждого запроса выведите «YES» (без кавычек), если существует минимальное остовное дерево со всеми данными ребрами, и «NO» (конечно же, без кавычек) иначе.

Примечание

На рисунке граф из первого примера:

Вес минимального остовного дерева равен 6.

Минимальное остовное дерево из ребер (1, 3, 4, 6) содержит все ребра из первого запроса, поэтому ответ на первый запрос «YES».

Ребра из второго запроса образуют цикл длины 3, поэтому не существует остовного дерева, включающего в себя эти три ребра. Поэтому ответ «NO».


Примеры
№Входные данныеВыходные данные
1 5 7
1 2 2
1 3 2
2 3 1
2 4 1
3 4 1
3 5 2
4 5 2
4
2 3 4
3 3 4 5
2 1 7
2 1 2 
YES
NO
YES
NO

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет