eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Зв`язність графа

Зв`язність графа

Задано зв'язний неорієнтовний граф. Вам поступають запити виду: перевірити, чи залишиться граф зв'язним після видалення деякої маленької множини ребер. \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}" у протилежному випадку.
Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
4 5
1 2
2 3
3 4
4 1
2 4
3
1 5
2 2 3
2 1 2
Вихідні дані #1
Connected
Disconnected
Connected