평면 그래프의 짝수 사이클 분할

정점 이중연결 [1] 평면 [5] 그래프 [3] $G$가 주어진다. 이 그래프에서 홀수 개의 간선으로 둘러싸인 면 [7]은 많아야 두 개다. $G$를 평면에 그린 평면 그리기 [6]도 함께 주어진다. $G$의 간선 전체를 길이가 짝수인 단순 사이클 [8] 여러 개로 나눌 수 있는지 판별하여라.

[1] 정점 이중연결 그래프는 모든 $v \in V$에 대해 $(V \setminus \{v\}, E)$가 연결 그래프 [2]가 되는 그래프 $G = (V, E)$다.

[2] 연결 그래프는 다음을 만족하는 그래프 $G = (V, E)$다. $V$를 공집합이 아닌 두 부분집합 $V_1, V_2 \subseteq V$로 $V_1 \cap V_2 = \emptyset$, $V_1 \cup V_2 = V$가 되게 나눌 때마다, $u \in V_1$이고 $v \in V_2$인 간선 $uv \in E$가 존재한다.

[3] 그래프는 순서쌍 $(V, E)$이며, $E$는 $V$의 두 원소짜리 부분집합으로 이루어진 다중집합 [4]이다.

[4] 다중집합은 같은 원소가 여러 번 들어갈 수 있는 집합이다. 형식적으로는 임의의 집합에서 자연수 집합으로 가는 함수다.

[5] 그래프 $G = (V, E)$를 평면에 그리는 평면 그리기 [6]가 존재하면 $G$를 평면 그래프라고 한다.

[6] 평면 그래프의 평면 그리기는 각 정점에 평면 위의 서로 다른 점을 대응시키고, 각 간선에는 그 간선이 잇는 두 정점의 점을 잇는 곡선을 대응시킨 그림이다. 각 곡선은 다른 정점이나 다른 곡선과 자기 끝점에서만 만난다.

[7] 평면 그래프의 평면 그리기 하나를 생각하자. 간선에 대응하는 곡선으로 둘러싸인 평면의 각 영역을 그래프의 면이라고 한다. 어느 그래프에나 그래프를 감싸는 무한한 면이 하나 있다는 점에 주의한다.

[8] 간선의 부분집합 $C \subseteq E$가 연결 그래프를 이루고 그 그래프의 모든 정점이 정확히 두 간선과 인접하면, $C$를 단순 사이클이라고 한다.

첫 줄에 정수 $n$과 $m$이 주어진다 ($2 \le n \le 1\,000\,000$, $1 \le m \le 5\,000\,000$). $n$은 그래프 $G$의 정점 수, $m$은 간선 수다. 정점에는 $1$부터 $n$까지, 간선에는 $1$부터 $m$까지 번호가 붙어 있다. 각 간선은 서로 다른 두 정점을 잇는다. 한 정점 쌍 사이에 간선이 여러 개 있을 수도 있다.

다음 $n$개의 줄에는 그래프의 간선 정보가 주어진다. 그중 $i$번째 줄은 정점 $i$와 인접한 간선을 설명한다. 이 줄은 정수 $s_i$ ($1 \le s_i \le m$)로 시작하고, 그 뒤에 $1$ 이상 $m$ 이하인 정수 $s_i$개가 이어진다. 각 정수는 정점 $i$와 인접한 간선의 번호이며, 정점 $i$ 둘레를 시계 방향으로 돈 순서대로 나열되어 있다.

$G$의 간선 전체를 길이가 짝수인 단순 사이클로 나눌 수 있으면 첫 줄에 TAK을 출력하고, 그런 분할이 없으면 NIE를 출력한다.