부르들로의 세 왕국

당신은 고대 부르들로 세 왕국의 왕조를 연구하는 계보 연구소의 고고학자다. 유적을 발굴하다가 이 왕조들을 기록한 문서를 여러 장 찾아냈다. 세 왕국의 초기 역사는 알려진 것이 없고 많은 왕과 왕비의 이름도 남아 있지 않아, 이 문서가 왕가의 혈연 관계를 알려 주는 유일한 기록이다.

문서는 여러 줄로 이루어지고, 각 줄에는 왕족 두 사람의 이름이 적혀 있다. 두 줄짜리 문서의 예는 다음과 같다.

Alice Bob
Bob Clare

각 줄은 원래 완전한 문장이었지만 문서가 심하게 훼손되어 한 줄에서 이름 두 개만 읽어 낼 수 있다. 모든 줄을 참인 조상 관계로 읽으면 모순이 생긴다. 어떤 문서는 부정문으로 읽어야 조상 관계를 모순 없이 이해할 수 있다. 각 문서는 긍정 문서이거나 부정 문서다.

긍정 문서에서는 각 줄의 왼쪽 사람이 오른쪽 사람의 조상이다. 위 문서를 긍정 문서로 읽으면 "Alice는 Bob의 조상이고, Bob은 Clare의 조상이다"가 된다.
부정 문서에서는 각 줄의 왼쪽 사람이 오른쪽 사람의 조상이 아니다. 위 문서를 부정 문서로 읽으면 "Alice는 Bob의 조상이 아니고, Bob은 Clare의 조상이 아니다"가 된다.

한 문서 안에서 긍정과 부정이 섞이는 일은 없다. 위 문서를 "Alice는 Bob의 조상이고, Bob은 Clare의 조상이 아니다"로 읽을 수는 없다.

어느 줄에도 직접 적히지 않은 조상 관계를 다음 규칙으로 알아낼 수 있다. 임의의 사람 $x$ , $y$ , $z$ 에 대해 $x$ 가 $y$ 의 조상이고 $y$ 가 $z$ 의 조상이면 $x$ 는 $z$ 의 조상이다. 그래서 위 문서를 긍정 문서로 읽으면 "Alice Clare"라는 조상 관계도 얻는다.

당신은 " $p$ 가 $q$ 의 조상이다"라는 가설 하나를 확인하려 한다. 어느 문서가 긍정이고 어느 문서가 부정인지는 알 수 없다. 문서들과 서로 다른 두 이름 $p$ , $q$ 가 주어질 때, 이 가설과 모순되지 않는 해석이 있는지 판정하라. 어떤 해석이 가설과 모순된다는 말은, 그 해석과 가설에서 어떤 두 사람 $x$ , $y$ 에 대해 다음 중 하나를 알아낼 수 있다는 뜻이다.

$x$ 가 $y$ 의 조상이면서 $y$ 가 $x$ 의 조상이다.
$x$ 가 $y$ 의 조상이면서 $x$ 가 $y$ 의 조상이 아니다.

문서에 나오는 사람은 저마다 이름이 하나뿐이다. 두 사람이 같은 이름을 쓰지 않고, 한 사람이 여러 이름으로 나오지도 않는다.

$A$ 가 $B$ 의 조상이라는 말은 $A$ 가 $B$ 의 부모, 조부모, 증조부모 등이라는 뜻이다. 어느 문서에도 나오지 않는 사람이나 조상 관계가 있어도 된다. 그림 1의 가계도라면 다음 긍정 문서가 가능하다.

A H
B H
D H
F H
E I

여기서 C와 G는 나오지 않고, "A E", "D F", "C I" 같은 조상 관계도 나오지 않는다.

가계도

그림 1. 가계도

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

p q
n
c_1
...
c_n

첫 줄에는 서로 다른 두 이름 $p$ 와 $q$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 문서의 개수 $n$ 이 주어진다. 이어서 문서 $n$ 개의 설명이 주어진다.

$i$ 번째 문서 $c_i$ 의 형식은 다음과 같다.

m_i
x_{i,1} y_{i,1}
...
x_{i,m_i} y_{i,m_i}

첫 줄에는 그 문서에 적힌 이름 쌍의 개수 $m_i$ 가 주어진다. 이어지는 $m_i$ 개의 줄에는 서로 다른 두 이름 $x_{i,j}$ 와 $y_{i,j}$ ( $1 \le j \le m_i$ )가 공백으로 구분되어 주어진다.

이름은 영어 소문자와 대문자로만 이루어지고 길이는 1 이상 5 이하다. 두 이름은 완전히 같을 때만 같은 이름이므로 a와 A는 서로 다른 사람의 이름이다.

테스트 케이스는 다음 조건을 만족한다.

$1 \le n \le 1000$
$1 \le m_i$
$\sum_{i=1}^{n} m_i \le 100000$ , 즉 문서에 적힌 이름 쌍의 총 개수는 $100000$ 개 이하다.
테스트 케이스에 나오는 서로 다른 이름은 $300$ 개 이하다.

부르들로의 세 왕국

문제

입력

출력