Компанія з мережевих технологій#3423
Уявіть, що ви є консультантом для мережевої компанії CluNet, яка стикається з наступною проблемою. Мережа, над якою вони працюють, представлена зв'язаним графом G = (V, E) з вузлами та ребрами. Кожне ребро є волоконно-оптичним кабелем, що належить одній з двох компаній — або — і орендоване CluNet. Їхній план полягає у виборі остовного дерева графа для модернізації з'єднань, що відповідають ребрам . Вони вже уклали угоду з компаніями та , яка передбачає число , так що в обраному дереві ребер будуть належати , а N - K - 1 ребер будуть належати .
Керівництво CluNet стикається з проблемою: вони не впевнені, чи існує остовне дерево, яке відповідає цим умовам, і як його знайти, якщо воно існує. Це завдання, яке вони доручають вам.
Вхід містить кілька тестових випадків.
Кожен тестовий випадок починається з рядка, що містить три цілі числа (1 \leq N \leq 1000), (1 \leq M \leq 3000) та (0 \leq K \leq N - 1).
Наступні рядків описують ребра. -й рядок містить три цілі числа x_i, y_i та c_i. -те ребро з'єднує x_i-ту та y_i-ту вершини. c_i вказує на компанію, якій належить -те ребро: означає , а означає .
Вхід закінчується рядком, що містить три нулі. Цей рядок не повинен оброблятися.
Для кожного тестового випадку виведіть відповідь, як показано у зразку виводу. Перший рядок кожного виводу повинен вказувати номер тестового випадку, починаючи з .
У наступному рядку виведіть possible або impossible. Якщо ви можете побудувати остовне дерево, що задовольняє умову, виведіть possible. Інакше виведіть impossible.
Якщо ви можете побудувати остовне дерево, виведіть у наступному рядку номери ребер (починаючи з ), які ви використали. Кожне число повинно бути відокремлене одним пробілом.
Ви повинні вивести порожній рядок після кожного тестового випадку.
Приклад 1