동전 진술
시간 제한1초메모리 제한128 MB
위치 i가 X이거나 위치 j가 Y라는 형태의 N개 조건이 주어질 때 모든 조건을 만족하는 P/G 수열을 하나 구성하거나 불가능함을 판단하는 문제입니다(2-SAT).
문제
John과 Ted는 동전 결과로 이루어진 문자열을 맞히는 게임을 하고 있다.
John은 여러 개의 동전을 탁자 위에 놓는다. 그런 다음 동전을 하나씩 다시 집어 들면서, 위쪽 면이 앞면이면 P, 뒷면이면 G를 적는다. 이렇게 하면 P와 G로만 이루어진 길이 L의 무작위 문자열이 만들어진다.
그 뒤 John은 N개의 문장을 말한다. 각 문장은 다음과 같은 형태이다.
i번째 문자는 X이거나, j번째 문자는 Y이다
여기서 i와 j는 서로 다른 위치이고, X와 Y는 각각 P 또는 G 중 하나이다. John이 말한 모든 문장은 두 주장 중 적어도 하나가 참이다.
Ted는 John의 문장만 듣고, 그 문장들을 모두 참으로 만들 수 있는 문자열을 하나 찾고 싶다. 그런 문자열이 존재하면 하나 출력하고, 존재하지 않으면 없다고 판단하는 프로그램을 작성하라.
입력
첫째 줄에 문자열의 길이 L이 주어진다 (2 <= L <= 1000).
둘째 줄에 문장의 개수 N이 주어진다 (1 <= N <= 100000).
다음 N개의 줄에는 문장 하나가 다음 형식으로 주어진다.
i X j Y
1 <= i, j <= L, i != j를 만족하며, X와 Y는 모두 P 또는 G이다.
출력
모든 문장을 만족하는 문자열 하나를 출력한다.
그런 문자열이 존재하지 않으면 -1을 출력한다.
가능한 문자열이 여러 개일 수 있으며, 그중 아무거나 출력해도 된다.