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

시간 제한1초메모리 제한128 MB

요약

홀수 면이 최대 두 개인 이중 연결 평면 그래프의 간선을 짝수 길이 단순 사이클들로 분할할 수 있는지 판정합니다.

난이도: 어려움10점 중 9점
유형: 그래프, 수학
정답자: 아직 제출이 없습니다

문제

정점 이중연결 [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를 출력한다.

예제3

예제 1

입력

10 16
2 1 8
2 8 7
4 1 9 2 14
4 6 13 7 14
4 16 10 9 15
4 16 15 13 12
4 2 10 3 11
4 5 12 6 11
2 3 4
2 4 5

예상 출력

TAK

예제 2
입력
```
3 3
2 3 1
2 1 2
2 2 3
```
예상 출력
```
NIE
```
예제 3
입력
```
4 4
2 4 1
2 1 2
2 2 3
2 3 4
```
예상 출력
```
TAK
```