Задача Conflict
З полярниками – героями задачі Ferry сталася звична для
дослідників історія – про них забули. Добре, що запасів
продовольства та пального було на довгі роки. Так і
працювали – не зважаючи ні на що день за днем. Але
почав спрацьовувати фактор психологічної сумісності:
люди, що мусять довго спілкуватися в межах замкненого
кола осіб, з часом інколи починають не сприймати один
одного. Психологи вважають, що таке ставлення завжди
взаємне і завжди проявляється між парами осіб, незалежно
від присутності чи відсутності інших. Для виконання
чергової серії досліджень полярникам потрібно
розділитися на дві групи, які певний час працюватимуть
окремо одна від одної. Допоможіть з’ясувати, як
розподілити всіх полярників по двом групам так, щоб
всередині кожної групи не було потенційно конфліктних
пар.
Технічні умови: Програма читає з клавіатури кількість
полярників N (3<=N<=10000), потім кількість потенційно
конфліктних пар M (0<=M<=20000), потім самі пари, в яких
полярники задані їхніми номерами від 1 до
N. Програма
виводить на екран у першому рядку 0 (якщо розподілити
полярників потрібним чином неможливо) або 1 (якщо
можливо). Якщо розподіл можливий, то 2-ий та
3-ій рядки
повинні містити розділені пропусками списки полярників,
віднесених до відповідної групи. Дбати про те, щоб
розміри груп були (хоча б приблизно) однаковими, не
потрібно, але обидві групи мають виявитися не порожніми.
Якщо правильних відповідей кілька, виводьте будь-яку з
них.
Приклад_1
Введення
5 3 1 2 1 4 3 5
Виведення
1
1 3
2 4 5
Приклад_2
Введення
5 5 1 5 1 4 1 3 2 5 5 3
Виведення
0
Задача Conflict
С полярниками – героями задачи Ferry произошла обычная
для исследователей история – о них забыли. Хорошо, что
запасов продовольствия и топлива хватало на долгие годы.
Так и работали – не обращая внимания ни на что день за
днем. Однако начал проявляться фактор психологической
совместимости: люди, вынужденные долго общаться в узком
кругу, со временем иногда начинают не переносить друг
друга. Психологи считают, что такое отношение всегда
взаимно и всегда проявляется между парами людей,
независимо от присутствия или отсутствия
других. Для
проведения очередной серии исследований полярникам нужно
разделиться на две группы, которые некоторое время будут
работать отдельно одна от другой. Помогите распределить
всех полярников на две группы так, чтобы в составе каждой
группы не было потенциально конфликтных пар.
Технические условия: Программа читает с клавиатуры
количество полярников N (3<=N<=10000), затем количество
потенциально конфликтных пар M (0<=M<=20000), затем сами
пары, в которых полярники заданы их номерами от 1 до
N.
Программа выводит на экран в первой строке 0 (если
распределить полярников нужным образом невозможно) либо
Примеры
Ввод
5 3 1 2 1 4 3 5
Вывод
1
1 3
2 4 5
Ввод
5 5 1 5 1 4 1 3 2 5 5 3
Вывод
0