우체부

매일 아침 우체부 바이트아사르는 자신이 맡은 구역의 모든 거리를 지나며 우편물을 배달해야 한다. 모든 도로는 일방통행이며 교차로들을 연결한다. 교차로에는 $1$번부터 $n$번까지 번호가 매겨져 있고, 어떤 두 교차로 사이에는 서로 반대 방향의 도로가 각각 하나씩, 최대 두 개까지 있을 수 있다.

바이트아사르는 매번 $1$번 교차로에 있는 우체국에서 경로를 시작하고 그곳에서 끝낸다. 예전에는 경로를 스스로 정했지만, 이제는 규정에 따라 선택이 제한된다. 그는 여러 개의 경로 조각, 즉 교차로 번호들의 수열 여러 개를 배정받는다. 바이트아사르가 선택하는 경로는 다음 조건을 모두 만족해야 한다.

• 모든 거리를 정확히 한 번씩 지난다.
• 배정된 각 수열을, 연속으로 방문하는 교차로들의 한 구간으로 포함한다. 즉, 그 수열이 경로의 연속한 원소 $v_i, v_{i+1}, \dots$ 로 나타난다.
• $1$번 교차로에서 시작하여 $1$번 교차로에서 끝난다.

이 모든 조건을 만족하는 경로가 존재하지 않을 수도 있다. 예를 들어 배정된 수열이 존재하지 않는 도로를 지나도록 요구할 수 있다. 이러한 경로가 존재하는지 여부만 판정하여라.

첫 번째 줄에 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 50000$, $1 \le m \le 200000$). 각각 교차로의 수와 도로의 수이다.

이어지는 $m$개의 줄에는 도로가 하나씩 주어진다. 각 줄에는 두 정수 $a$와 $b$가 있으며 ($1 \le a, b \le n$, $a \ne b$), $a$번 교차로에서 $b$번 교차로로 향하는 일방통행 도로를 뜻한다. 각 순서쌍 $(a, b)$는 최대 한 번만 등장한다.

그 다음 줄에는 배정된 수열의 개수를 나타내는 정수 $t$가 주어진다 ($0 \le t \le 10000$). 이어지는 $t$개의 줄에는 수열이 하나씩 주어지는데, 각 줄은 정수 $k$ ($2 \le k \le 200000$)와 그 뒤에 오는 $k$개의 교차로 번호로 이루어진다. 모든 수열의 길이의 합은 $1000000$을 넘지 않는다.

한 줄에 다음을 출력한다.

• 조건을 모두 만족하는 경로가 존재하면 TAK,
• 그러한 경로가 존재하지 않으면 NIE.

(TAK과 NIE는 각각 폴란드어로 "예"와 "아니오"를 뜻한다.)