Surreal

트리는 재귀적으로 정의된다. 노드 하나는 트리이다. 트리가 루트 노드의 왼쪽 자식 또는 오른쪽 자식이 되어도 트리이다. 두 트리가 각각 루트 노드의 왼쪽 자식과 오른쪽 자식이 되어도 트리이다. 이 세 규칙을 유한번 적용해 만들어지는 구조를 모두 트리라고 한다. 즉 여기서 말하는 트리는 공집합이 아니고, 왼쪽 자식과 오른쪽 자식을 구별하는 루트 달린 이진 트리이다.

두 트리 $T$, $T'$는 다음 네 조건 중 하나를 만족하면 동형($T \equiv T'$)이다. (1) 둘 다 노드 하나로 이루어져 있다. (2) 각 루트에 왼쪽 자식만 있고, 왼쪽 부분트리끼리 동형이다. (3) 각 루트에 오른쪽 자식만 있고, 오른쪽 부분트리끼리 동형이다. (4) 각 루트에 왼쪽 자식과 오른쪽 자식이 모두 있고, 왼쪽 부분트리끼리, 오른쪽 부분트리끼리 각각 동형이다. 즉 노드에 번호를 붙이지 않고 왼쪽 자식과 오른쪽 자식만 구별했을 때 모양이 같으면 동형이다.

동형은 동치관계이며, 동형인 트리는 같은 트리로 본다. 동형이 아닌 두 트리는 다르다고 한다.

잎은 자식이 없는 노드이다.

$T$의 잎 하나를 다른 트리 $T''$로 바꾼 결과가 $T'$와 동형이면, $T$는 한 번의 치환으로 $T'$가 될 수 있으며 $T \to T'$로 쓴다. $n \ge 1$인 자연수 $n$과 트리 $T_1, T_2, \dots, T_n$이 있어서 $T \equiv T_1 \to T_2 \to \dots \to T_n \equiv T'$가 성립하면, $T$는 치환으로 $T'$가 될 수 있으며 $T \to^* T'$로 쓴다.

한 번의 치환은 잎을 떼어내고 그 자리에 새 트리를 붙이는 것이다. 잎에서 더 큰 부분트리가 자라난다고 보면 된다. 치환은 0번, 1번, 여러 번 적용할 수 있으므로 모든 트리 $T$에 대해 $T \to^* T$가 성립한다. 노드 하나짜리 트리는 어떤 트리로든 변환할 수 있고, 어떤 트리든 서로 다른 트리 무한히 많은 것으로 변환할 수 있다.

트리 $T$에 대해 $\operatorname{grow}(T) = \{T' \mid T \to^* T'\}$로 정의한다. 유한 집합 $\mathscr{T} = \{T_1, T_2, \dots, T_n\}$에 대해서는 $\operatorname{grow}(\mathscr{T}) = \bigcup_{i=1}^{n} \operatorname{grow}(T_i)$로 정의한다. 트리들의 집합을 숲이라고 부른다. 공집합이 아닌 숲에서 자라난 숲은 무한하지만, 모든 트리를 포함하지는 않는다.

유한개의 트리만 빠져 있는 숲을 거의 완전하다고 한다. 주어진 유한 집합 $\mathscr{T}$에 대해, $T \notin \operatorname{grow}(\mathscr{T})$를 만족하는 트리 $T$가 유한개뿐인지 판정하라. 여기서 $T \notin \operatorname{grow}(\mathscr{T})$는 $T' \to^* T$를 만족하는 $T' \in \mathscr{T}$가 하나도 없다는 뜻이다.

각 테스트케이스에는 여러 개의 사례가 들어 있다. 첫 줄에는 사례의 개수 $T$가 양의 정수로 주어진다. 각 사례는 트리의 개수 $m$로 시작하고, 이어서 $m$개의 트리가 주어진다.

트리는 노드 수 $n$과 그다음 $n$줄로 주어진다. $i$번째 줄에는 노드 $i$의 왼쪽 자식 $l_i$와 오른쪽 자식 $r_i$가 음이 아닌 정수로 적혀 있다. 자식이 없으면 0으로 적는다. 따라서 잎은 $l_i = r_i = 0$이다. 노드 1이 루트이다. 노드 번호는 편의를 위한 것이며, 동형인 트리는 같은 트리로 본다.

한 사례의 $m$개 트리에는 동형인 트리가 중복되어 있을 수 있다. 동형류마다 하나씩만 남긴 집합을 $\mathscr{T}$라고 한다.

각 사례마다 한 줄을 출력한다. $\operatorname{grow}(\mathscr{T})$에 포함되지 않는 트리가 유한개뿐이면 Almost Complete를, 그렇지 않으면 No를 출력한다.

모든 테스트케이스에 대해 $\sum n \le 2 \times 10^6$, $\sum m \le 2 \times 10^6$, $\max h \le 2 \times 10^6$, $T \le 10^2$이다. 여기서 $\sum n$은 한 테스트케이스의 사례들에 등장하는 모든 트리의 노드 수 합이고, $\sum m$은 사례들에 등장하는 트리 개수의 합이다. $\max h$는 테스트케이스에 등장하는 트리의 최대 높이이며, 노드 하나로 이루어진 트리의 높이는 1이다.