다각형 게임

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

요약

볼록 다각형을 삼각분할한 뒤 검은 삼각형 하나가 주어지고, 두 사람이 번갈아 귀 삼각형을 잘라내어 검은 삼각형을 자르는 사람이 이긴다. 선공이 이기는지 판정한다.

난이도: 어려움10점 중 8점
유형: 게임 이론, 트리, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

두 사람이 다각형 게임을 한다. 꼭짓점이 $n$ 개인 볼록 다각형이, 서로 교차하지 않는 $n-3$ 개의 대각선으로 $n-2$ 개의 삼각형으로 나뉘어 있다. 대각선들은 다각형의 꼭짓점에서만 만난다. 삼각형 중 하나는 검은색이고 나머지는 모두 흰색이다.

두 사람은 번갈아 차례를 진행한다. 자기 차례가 되면 현재 다각형에서 대각선 하나를 따라 삼각형 하나를 잘라 낸다. 잘라 낼 수 있는 삼각형은 한 변이 대각선이고 나머지 두 변이 현재 다각형의 변인 삼각형뿐이며, 잘라 내면 그 삼각형은 다각형에서 제거된다. 검은색 삼각형을 잘라 내는 사람이 이긴다.

볼록 다각형이란, 내부의 임의의 두 점을 잇는 선분이 항상 다각형 안에 들어 있는 다각형을 말한다.

다각형의 정보를 읽어, 먼저 두는 사람에게 필승 전략이 있는지 판정하는 프로그램을 작성하라.

입력

첫째 줄에 다각형의 꼭짓점 개수를 나타내는 정수 $n$ 이 주어진다 ( $4 \le n \le 50000$ ). 다각형의 꼭짓점에는 시계 방향으로 $0$ 부터 $n-1$ 까지 번호가 매겨져 있다.

다음 $n-2$ 개의 줄에는 삼각형들의 정보가 주어진다. 그중 $i$ 번째 줄 ( $1 \le i \le n-2$ )에는 $i$ 번째 삼각형을 이루는 세 꼭짓점의 번호 $a$ , $b$ , $c$ 가 공백 하나로 구분되어 주어진다 (세 값은 모두 음이 아닌 정수이다). 가장 먼저 주어지는 삼각형이 검은색 삼각형이다.

출력

먼저 두는 사람에게 필승 전략이 있으면 TAK을, 없으면 NIE를 한 줄에 출력한다. (TAK과 NIE는 각각 폴란드어로 '예'와 '아니오'를 뜻한다.)

예제4

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