eolymp
bolt
Try our new interface for solving problems
Məsələlər

Связность графа

Связность графа

Дан связный неориентированный граф. Вам поступают запросы вида: проверить, останется ли граф связным после удаления некоторого маленького множества рёбер. \InputFile Первая строка входного файла содержит два числа - \textbf{N} и \textbf{M} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100000}), обозначающие число вершин и число рёбер, соответственно. Следующие \textbf{M} строк содержат описание рёбер. Каждая строка состоит из двух чисел \textbf{a} и \textbf{b} - номера вершин, соединяемых соответствующим ребром. В графе нет петель и кратных рёбер. Вершины графа нумеруются с единицы. Рёбра нумеруются с единицы в том порядке, в котором они заданы во входном файле. Следующая строка содержит единственное число \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{100000}), обозначающее число запросов. Следующие \textbf{K} строк содержат описание запросов. Каждое описание начинается с числа \textbf{C} (\textbf{1} ≤ \textbf{C} ≤ \textbf{4}), обозначающее число рёбер в запросе, далее следуют \textbf{C} чисел, обозначающих номера рёбер, входящих в запрос. Все рёбра, входящие в запрос, являются различными. \OutputFile Для каждого запроса выведите единственную строку. В \textbf{i}-й строке должно содержаться слово "\textbf{Connected}", если удаление всех рёбер из соответствующего запроса сохранит связность графа, и "\textbf{Disconnected}" в противном случае.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
4 5
1 2
2 3
3 4
4 1
2 4
3
1 5
2 2 3
2 1 2
Çıxış verilənləri #1
Connected
Disconnected
Connected