cho.sh

하이퍼바이저 MacrOS

아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

Bob은 하이퍼바이저 시스템 MacrOS를 개발하는 팀의 리더입니다. 이 시스템은 수많은 패키지로 이루어져 있고, 일부 패키지는 다른 패키지에 의존하므로 전체 시스템은 올바른 순서로 설치해야 합니다.

"패키지 B가 A에 의존한다"는 것은 A를 B보다 먼저 설치해야 한다는 뜻이며, 짧게 A B로 적습니다. 의존 관계는 추이적입니다. 즉, C가 B에 의존하고 B가 A에 의존하면 C도 A에 의존합니다. 서로 의존하는 두 패키지는 존재하지 않으므로, 의존 관계는 사이클이 없는 구조를 이룹니다.

예를 들어 다음과 같은 초기 의존 목록은

1 6
6 3
3 4
2 5

아래 의존 그래프를 만듭니다.

예시 의존 그래프

개발이 진행되면서 Bob에게는 두 종류의 사건이 전달됩니다.

  • 프로그래머가 새로운 의존 관계를 알려 줍니다. 1 A B로 적으며, A를 B보다 먼저 설치해야 한다는 뜻입니다(위의 A B와 같은 관계).
  • 고객이 질문을 합니다. 0 A B로 적으며, "A를 B보다 먼저 설치해야 하나요?"라는 뜻입니다. 모든 질문에는 확정된 답이 있습니다. 질문 시점에 이미 A와 B 사이에는 의존 관계가 존재하므로, "A가 먼저"와 "B가 먼저" 중 정확히 하나만 성립합니다.

Bob의 프로그램은 두 개의 로그를 남겼습니다. 첫 번째 로그에는 모든 사건의 기록이, 두 번째 로그에는 고객에게 준 답(A를 먼저 설치해야 하면 YES, B를 먼저 설치해야 하면 NO)이 들어 있습니다.

Bob은 첫 번째 로그를 당신에게 주기 전에 변형했습니다. 처음에는 뒤집기 스위치가 꺼져 있습니다. 어떤 질문의 올바른 답이 NO일 때마다 그는 뒤집기 스위치를 토글합니다. 스위치가 켜져 있는 동안에는 모든 프로그래머 줄 1 A B가 두 패키지를 맞바꾼 채로 저장됩니다(즉, 실제 의존 관계는 B A입니다). 질문 줄은 절대 바뀌지 않습니다. 당신은 Bob이 변형한 첫 번째 로그를 읽고 모든 고객 질문에 대한 답을 복원해야 합니다.

뒤집기 스위치는 테스트 케이스마다 독립적이며, 각 테스트 케이스가 시작될 때 꺼진 상태로 시작합니다.

다음 예시는 초기 의존 관계 1 6, 6 3, 3 4, 2 5(위 그래프)를 사용하며, 변형된 로그의 각 줄이 어떻게 해석되고 어떤 답이 나오는지 보여 줍니다.

변형된 로그 줄해석답
1 1 3의존 관계 1 → 3 추가
0 1 31이 3보다 먼저인가?YES
1 1 4의존 관계 1 → 4 추가
0 5 25가 2보다 먼저인가?NO — 스위치 켜짐
1 2 3스위치 켜짐, 3 → 2 추가
1 5 6스위치 켜짐, 6 → 5 추가
0 1 51이 5보다 먼저인가?YES
1 5 4스위치 켜짐, 4 → 5 추가
0 5 35가 3보다 먼저인가?NO — 스위치 꺼짐
1 1 2의존 관계 1 → 2 추가

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 Z≤15Z \le 15가 주어집니다. 이어서 각 테스트 케이스가 다음 형식으로 주어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 nn과 mm (1≤n≤1051 \le n \le 10^5, 0≤m≤1050 \le m \le 10^5)이 주어집니다. 각각 패키지의 수와 알파 테스트 이전에 알려진 의존 관계의 수입니다. 이어지는 mm개의 줄에는 각각 두 정수 AA와 BB (1≤A,B≤n1 \le A, B \le n)가 주어지며, 패키지 BB가 AA에 의존함(먼저 AA를 설치)을 뜻합니다. 같은 의존 관계가 여러 번 나올 수 있으며, 서로 의존하는 두 패키지는 없습니다.

테스트 케이스의 나머지 부분은 Bob이 변형한 로그입니다. 각 줄은 1 A B(새 의존 관계) 또는 0 A B(질문)입니다. 로그 줄의 수는 최대 10510^5개입니다. 로그와 테스트 케이스는 0 0 0 줄로 끝납니다.

출력

각 질문 줄 0 A B에 대해, 패키지 AA를 BB보다 먼저 설치해야 하면 YES를, 패키지 BB를 먼저 설치해야 하면 NO를 각각 한 줄에 출력합니다. 모든 질문에는 유일한 답이 있음이 보장됩니다.