문제

오늘 A 학교에서 번부터 번까지 번호가 매겨진 명의 학생이 미터 달리기 경주를 하려고 합니다.

이때 여러분은 다음과 같은 정보를 총 개 알고 있습니다.

• : 번 학생과 번 학생이 달리기 경주를 할 경우, 항상 번 학생이 결승선에 먼저 들어옵니다.

단, 여러분의 정보는 언제나 정확하기 때문에, 모순되는 정보는 주어지지 않습니다. 또한, 어떤 두 학생을 골라도 기록이 서로 같지 않습니다.

여러분은 이 명의 학생이 달리기 경주를 했을 때 결승선에 가장 먼저 들어온 명에게 상을 주려고 합니다. 그러던 중 여러분은 다음과 같은 고민에 빠졌습니다.

• 학생들의 기록이 어떻게 결정되어도 가장 먼저 들어온 명의 집합이 항상 동일하다면, 달리기 경주가 재미없게 됩니다.

예를 들어, 명의 학생이 있고 그 관계가 다음과 같다고 생각합시다. 에서 로 향하는 화살표는 번 학생이 항상 번 학생보다 먼저 들어옴을 의미합니다.

이때 라면 가장 먼저 들어온 명은 항상 번 학생과 번 학생이므로 달리기 경주가 재미없게 됩니다.

에 대해 각각, 명에게 상을 줄 때 달리기 경주가 재미없게 되는지 구하는 프로그램을 작성해 주세요.

입력

첫 번째 줄에 테스트 케이스의 개수 가 주어집니다.

그다음 줄부터 개의 테스트 케이스가 주어집니다. 테스트 케이스의 형식은 다음과 같습니다.

첫 번째 줄에는 두 정수 과 이 공백으로 구분되어 주어집니다.

두 번째 줄부터 개의 줄에 걸쳐 각각 정보를 나타내는 두 정수 와 가 주어집니다.

출력

각 테스트 케이스에 대해 길이 의 문자열 를 새로운 줄에 출력합니다. 이때 는 다음과 같이 정의됩니다.

• 일 때 경주가 재미없게 된다면 는 1입니다.
• 일 때 경주가 재미없게 되지 않는다면 는 0입니다.

채점

• 모든 테스트 케이스에서 의 합은 을 초과하지 않습니다.
• 모든 테스트 케이스에서 의 합은 을 초과하지 않습니다.
• 주어진 개의 정보는 항상 서로 다릅니다.
• 주어진 개의 정보는 모순되지 않습니다.

서브태스크

노트

첫 번째 테스트 케이스는 지문에 주어진 그림과 같습니다.

두 번째 테스트 케이스에서 명의 학생에 대해 알고 있는 정보는 다음과 같습니다.

• 번 학생은 번 학생보다 항상 먼저 들어옵니다.
• 번 학생은 번 학생보다 항상 먼저 들어옵니다.
• 번 학생은 번 학생보다 항상 먼저 들어옵니다.

이때 각 의 값에 대한 설명은 다음과 같습니다.

• 일 때 가장 먼저 들어온 학생은 항상 번 학생입니다.
• 일 때 가장 먼저 들어온 명의 집합은 또는 입니다.
• 일 때 가장 먼저 들어온 명의 집합은 또는 입니다.
• 일 때 가장 먼저 들어온 명의 집합은 입니다.

그러므로 또는 일 때 달리기 경주가 재미없게 됩니다.