도시 관광

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

요약

모든 꼭짓점의 차수가 4인 연결된 다중 그래프에서 각 변의 중점에 물건이 있을 때, 어떤 변의 중점에서 시작하는 닫힌 오일러 투어가 흥미도가 0 아래로 떨어지지 않게 존재하는지 판정한다.

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

문제

바이트랜드(Byteland)의 도시 바이텐부르크(Bytenburg)에서 오픈카 버스를 타고 거리를 도는 관광 상품을 준비하고 있다. 모든 관광은 회사 본부에서 출발해 본부에서 끝나며, 이 본부를 어느 거리 한가운데에 세울지 정해야 한다.

관광객이 무언가를 놓쳤다고 느끼지 않도록, 관광 경로는 도시의 모든 거리를 빠짐없이 지나야 한다. 거리는 곧게 뻗어 있지 않을 수 있고 터널이나 고가로 이어질 수도 있다. 일방통행 거리는 없다. 각 거리는 두 교차로를 잇고, 모든 교차로에서는 네 방향으로 거리가 뻗어 있다(즉 모든 교차로의 차수는 4이다). 두 교차로를 잇는 거리가 둘 이상일 수도 있다. 거리 중간에서는 방향을 되돌릴 수 없지만 교차로에서는 되돌 수 있다. 또한 거리망을 통해 어느 교차로에서든 다른 어느 교차로로도 갈 수 있다(그래프는 연결되어 있다).

각 거리의 정확히 한가운데에는 관광객이 볼 만한 대상(전망, 조각상, 기념물 등)이 하나씩 있다. 대상의 매력도는 음이 아닌 정수로 나타낸다. 본부는 이런 대상 하나의 옆, 즉 어떤 거리의 한가운데에 세운다.

관광이 진행되는 동안 관광객의 흥미는 다음과 같이 변한다.

버스로 $1$ byte-mile를 이동할 때마다 흥미가 $1$ 줄어든다.
어떤 대상을 처음 볼 때, 그 대상의 매력도만큼 흥미가 늘어난다.
관광 시작 시점의 흥미는 본부가 있는 거리의 대상의 매력도와 같다.

관광 경로가 진행되는 동안 흥미가 한 번도 $0$ 아래로 떨어지지 않으면 그 경로를 매력적(attractive)이라고 한다.

주어진 도시에서 매력적인 관광 경로가 존재하는지 판정하는 프로그램을 작성하라.

입력

첫째 줄에 교차로의 수 $n$ 이 주어진다 ( $1 < n \le 10\,000$ ). 교차로는 $1$ 부터 $n$ 까지 번호가 매겨져 있고, 거리는 $1$ 부터 $2n$ 까지 번호가 매겨져 있다.

이어지는 $2n$ 개의 줄에 거리 정보가 하나씩 주어진다. $i+1$ 번째 줄에는 $i$ 번째 거리를 나타내는 네 정수 $a$ , $b$ , $l$ , $s$ 가 공백으로 구분되어 주어진다. $a$ 와 $b$ 는 이 거리가 잇는 두 교차로의 번호로 $1 \le a, b \le n$ 이고 $a \ne b$ 이다. $l$ 은 짝수이며 이 거리의 길이(byte-mile)로 $2 \le l \le 1000$ 이다. $s$ 는 이 거리 한가운데 있는 대상의 매력도로 $0 \le s \le 1000$ 이다.

출력

매력적인 관광 경로가 존재하면 첫째 줄에 TAK을, 존재하지 않으면 NIE를 출력한다. (TAK과 NIE는 각각 폴란드어로 "예"와 "아니오"를 뜻한다.)

예제3

예제 1

입력

예상 출력

TAK

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