Игра в 2-SAT
Это интерактивная задача.
На экзамене по теории сложности Пете попалась следующая задача. Дано логическое выражение в виде 2-КНФ. Задача состоит в том, чтобы определить, можно ли присвоить переменным значения true или false таким образом, чтобы значение данного выражения стало true.
Логическое выражение содержит переменные, каждая из которых может принимать значения true или false. Выражение в виде 2-КНФ устроено следующим образом:
- Выражение в 2-КНФ — это конъюнкция (то есть операция «и») одного или нескольких дизъюнктов.
- Каждый дизъюнкт — это операция «или», применённая к двум различным переменным или их отрицаниям.
- Переменная может входить больше чем в один дизъюнкт.
- Могут существовать переменные, которые не входят ни в один дизъюнкт.
Вот несколько примеров выражений в 2-КНФ (символы «&», «|», «!» означают соответственно «и», «или», «не»):
- (a|b)&(c|!d)
- (!a|!b)
- (a|b)&(a|!b)&(b|!c)
Петя решил, что ответ на задачу — «невозможно». Теперь ему предстоит доказать это учителю. Для этого учитель предложил ему сыграть в интересную игру.
В начале игры ни одной из переменных из данного выражения не присвоено значение. Петя и учитель ходят по очереди, начиная с Пети. На каждом ходу игрок выбирает любую переменную, которой ещё не присвоено значение, и присваивает ей true или false. Когда всем переменным уже присвоено значение, игра заканчивается.
Если при подстановке полученных значений переменных в данное выражение получается false, то считается, что Петя выиграл игру, успешно доказал свой ответ и сдал экзамен. Если же получается true, то ответ Пети, очевидно, ошибочен, и экзамен он не сдал.
Помогите Пете сдать экзамен. Напишите программу, которая будет играть в эту игру за Петю. Если у Пети не существует выигрышной стратегии, нужно сразу же об этом сообщить, чтобы не тратить время на проигрышную игру.
Сначала на вход вашей программе подаётся выражение в виде 2-КНФ. В первой строке заданы числа n и m — количество переменных и дизъюнктов (2 ≤ n ≤ 104, 1 ≤ m ≤ 2·104).
Далее в m строках заданы дизъюнкты. Дизъюнкт задаётся двумя числами — номерами переменых. Если переменная входит в дизъюнкт с отрицанием, то её номер задан со знаком минус. Переменные нумеруются с единицы.
Если у Пети нет выигрышной стратегии, программа должна вывести «-1 -1» и завершиться.
В противном случае начинается игра. Ваша программа играет за Петю, а программа жюри — за учителя. Каждый ход игрок, который его выполняет, печатает два целых числа. Присваивание переменной с номером x значения v задается строкой «x v». Чтобы присвоить значение false, необходимо вывести значение v = 0, а чтобы присвоить значение true, необходимо вывести значение v = 1.
Ход Пети ваша программа должна вывести в стандартный поток вывода. После каждого своего хода, если игра не закончилась, ваша программа получит в стандартный поток ввода очередной ход учителя в таком же формате.
По окончании игры ваша программа должна завершиться.
После каждого действия вашей программы выводите символ перевода строки. Если вы используете «writeln» в Паскале, «cout << ... << endl» в C++, «System.out.println» в Java или «print» в Python, сброс потока вывода у вас происходит автоматически, дополнительно делать «flush» не обязательно. Если вы используете другой способ вывода, рекомендуется делать «flush», но всё равно обязательно требуется выводить символ перевода строки.
Ниже приведены наиболее типичные причины получения тех или иных сообщений об ошибке.
Если ваша программа соблюдает протокол, но в конце игры значение данного выражения равно true, то вы получите результат «Wrong Answer».
Если ваша программа вывела вместо первого хода «-1 -1», но у вас была выигрышная стратегия, то вы получите результат «Wrong Answer».
Если ваша программа выводит некорректно отформатированные сообщения программе жюри, то вы получите результат «Wrong Answer».
Если ваша программа нарушила протокол и ждёт ввода в то же время, когда его ждёт и программа жюри, то вы получите результат «Idleness Limit Exceeded». Обратите внимание, что к такому же результату может привести и то, что вы не переводите строку после каждого выведенного сообщения или выводите не тем способом, который описан в начале раздела, и не делаете «flush».
3 2
1 2
-1 -2
2 0
3 1
1 0
2 2
1 2
-1 -2
-1 -1