시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 0 0 0.000%

문제

두 논리식이 주어졌을 때, 두 논리식이 논리적으로 같은지 아닌지를 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 같은지 비교해야 할 두 논리식이 주어진다. 입력으로 주어지는 식은 26개의 변수 a-z, 이항 연산자 |, &, ^,(OR, AND, XOR), 단항 연산자 ~(NOT), 괄호로 이루어져 있다. 

이외의 다른 문자는 무시해야 하고, C언어 연산자 우선순위를 따른다. 두 입력식은 구분되어 있지 않다. 두 논리식을 구분하는 것도 구현해야 한다.

이러한 문제를 풀 때는 보통 각 식을 정규화 한 뒤, 두 정규화 식이 같은지 판별하는 방법을 사용한다. 각각의 논리식은 10개 이하의 변수, 100개 이하의 연산자로 이루어져 있다.

출력

각각의 테스트 케이스에 대해서, 두 논리식이 같다면,

Data set N: Equivalent

다르다면

Data set N: Different

를 출력한다. N은 테스트 케이스 번호이고, 1번부터 시작한다.

예제 입력

3
a ^b&(b|a)~b^ a
a^b&(b|a)(a^(b&(b|a)))
~~~~z~~z

예제 출력

Data set 1: Different
Data set 2: Equivalent
Data set 3: Equivalent

힌트