과일 무게 비교

시간 제한1초메모리 제한128 MB

요약

여러 과일 무게의 배수 사이 부등식이 주어질 때 질의식이 어느 방향으로 반드시 성립하는지 판정합니다.

난이도: 보통10점 중 7점
유형: 최단 경로, 그래프
정답자: 아직 제출이 없습니다

문제

과일끼리 무게를 비교해 보자. 이 문제에서 같은 종류의 과일은 모두 똑같고 무게도 같으며, 무게는 항상 양수이다.

비교 하나는 $a X \le b Y$ 형태로 주어진다. $a$ 와 $b$ 는 양의 정수, $X$ 와 $Y$ 는 과일 이름이고, 종류가 $X$ 인 과일 $a$ 개의 무게가 종류가 $Y$ 인 과일 $b$ 개의 무게보다 작거나 같다는 뜻이다.

비교 여러 개가 주어졌을 때, 또 다른 비교의 결과를 판정하라.

입력

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 주어지는 비교의 개수 $n$ 이 있다. 이어지는 $n$ 개 줄에는 비교가 a X b Y 형태로 하나씩 주어지며, 이는 $a X \le b Y$ 를 뜻한다. 테스트 케이스의 마지막 줄에는 같은 형태의 질의 a X b Y가 있고, $a X$ 와 $b Y$ 를 비교해야 한다.

$n = 0$ 인 줄은 입력의 끝을 나타내며 처리하지 않는다. 마지막 $n = 0$ 을 제외하면 입력에 나오는 정수는 모두 양수이고 100 이하이다. 과일 이름은 대소문자를 구분하는 영문자 문자열이며 길이는 50 이하이다.

출력

각 테스트 케이스마다 결과를 한 줄에 출력한다. 질의가 a X b Y일 때 결과는 다음 중 하나이다.

<=: $a X \le b Y$ 가 확실하다.
>=: $a X \ge b Y$ 가 확실하다.
==: $a X = b Y$ 가 확실하다. 즉 위의 두 결과를 모두 얻은 경우이다.
UNAVAILABLE: $a X$ 와 $b Y$ 의 대소를 전혀 확정할 수 없다. 즉 위의 세 결과 중 어느 것도 얻지 못한 경우이다.
INCONSISTENT: 주어진 비교에 모순이 있다. 즉 그 테스트 케이스의 비교를 모두 동시에 만족시킬 수 없음이 확실하다.

비교에 모순이 있으면 다른 결과보다 INCONSISTENT를 먼저 출력한다.

예제1

예제 1

입력

2
2 Orange 3 Apple
1 Apple 1 Peach
2 Orange 3 Peach
1
2 Orange 3 Apple
2 Orange 2 Apple
2
3 a 2 A
2 A 3 a
5 A 5 a
2
3 B 2 A
2 A 3 B
2 A 3 B
3
2 b 2 A
2 A 2 C
3 C 2 b
1 A 1 b
0

예상 출력

<=
UNAVAILABLE
>=
==
INCONSISTENT