오라, 부하여!

환영한다, 보물 사냥꾼! 나는 위대하고 강력한 우주 닌자이고, 너는 나의 부하다. 우리는 이 행성을 악당 "Dialog Not Found"로부터 구하기 위해 서둘러야 한다. 나는 "Dialog Not Found"의 악행 계획을 막으려면 땅 곳곳을 가로질러 이동해야 한다. 그런데 부하야, 나는 수많은 시련을 이겨내지 못한다. 누군가 나를 쳐다보는 것, 악수, 심지어 계단도 그중 하나다.

지도에는 위치들, 위치 사이의 경로, 그리고 각 경로에 놓인 시련이 주어진다. 닌자가 목표에 도달하도록 도와라. 닌자는 이겨내지 못하는 시련이 놓인 경로를 피해야 한다. 닌자가 목표에 도달할 수 있는지 판단하고, 도달할 수 있으면 세계를 구할 수 있다고 알려줘라.

첫 줄에는 확인할 지도의 개수 m이 양의 정수로 주어진다. 각 지도는 닌자가 이겨내지 못하는 시련의 개수 t(0 <= t <= 50)로 시작한다. 다음 t줄에 시련이 한 줄에 하나씩 적혀 있다. 그다음 줄에는 위치의 개수 n(2 <= n <= 30)과 경로의 개수 e(0 <= e <= 500)가 주어진다. 위치는 0부터 n-1까지 번호가 붙고, 닌자는 0에서 출발해 n-1을 목표로 한다.

이어지는 e줄에는 정수 La, Lb와 경로에 놓인 시련 문자열 Q가 주어진다. 닌자는 경로의 시련 Q가 이겨내지 못하는 시련 목록에 없을 때에만 La와 Lb 사이를 양방향으로 이동할 수 있다. 두 위치를 잇는 경로는 최대 하나이고, 각 경로에는 시련이 정확히 하나 있다. 시련 이름은 소문자로만 이루어지며 길이는 1 이상 20 이하다. 닌자의 목록에 없는 시련은 이겨낼 수 있다. 한 줄의 값들은 공백 한 칸으로 구분되며, 줄의 앞뒤에는 공백이 없다.

지도마다 한 줄에 닌자가 목표에 도달할 수 있으면 1, 도달할 수 없으면 0을 출력한다.