Problem : 150 - 鐵路

Special Judge

Problem Statistics

Solved Member: 6　　Submission: 56　　User Tried: 13

Statement:

還記得這題嗎?

由於火車站的擴建，暫時停放火車的區域從一條增為兩條，如下圖的 1 和 2 所示。

每台火車能夠從月台 A 到1,2兩個暫時停放的地方，或者把1,2暫時停放區域最前面的火車給移到 B 月台。
假設火車在 A 月台出發的順序為 A1,A2,...,An，我們希望火車抵達 B 月台的順序為 1,2,...,n，請問有沒有可能達成呢？

Input:Output:

第 1 行有一個整數 n(2 ≤ n ≤ 100000)，代表總共有幾列火車。
第 2 行有 n 個數字 A1,A2,...,An，為一 1 到 n 的排列，月台 A 火車出發的順序。

輸出第一行若有可能請輸出"TAK"，否則輸出"NIE"。
若有可能，第二行請輸出 n 個數字，每個數字為 1 或 2之一，代表第 i 台火車需要進到哪個暫存的軌道。

Sample Input:Sample Output:

A:
4
1 3 4 2

B:
4
2 3 4 1

A:
TAK
1 1 2 1

B:
NIE

HINT:

範例輸入以及輸出 A：
編號 1 的火車進了暫存軌道 1，然後馬上走到B。
編號 3 的火車進了暫存軌道 1，編號 4 的火車進了暫存軌道 2。
編號 2 的火車進了暫存軌道 1，然後馬上走到B。
接著編號 3 以及 4 的火車依序走到B。

Source:

POI 17 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	131072kb
0-2	1000ms	131072kb
1-ocen	1000ms	131072kb
1-1	1000ms	131072kb	10
1-2	1000ms	131072kb
1-3	1000ms	131072kb
1-4	1000ms	131072kb
2-ocen	1000ms	131072kb
2-1	1000ms	131072kb	10
2-2	1000ms	131072kb
2-3	1000ms	131072kb
3-ocen	1000ms	131072kb
3-1	1000ms	131072kb	10
3-2	1000ms	131072kb
3-3	1000ms	131072kb
4-ocen	1000ms	131072kb
4-1	1000ms	131072kb	10
4-2	1000ms	131072kb
4-3	1000ms	131072kb
5-1	1000ms	131072kb	10
5-2	1000ms	131072kb
5-3	1000ms	131072kb
6-1	2000ms	131072kb	10
6-2	2000ms	131072kb
6-3	2000ms	131072kb
7-1	2000ms	131072kb	10
7-2	2000ms	131072kb
7-3	2000ms	131072kb
8-1	2000ms	131072kb	10
8-2	2000ms	131072kb
8-3	2000ms	131072kb
9-1	2000ms	131072kb	10
9-2	2000ms	131072kb
9-3	2000ms	131072kb
10-1	2000ms	131072kb	10
10-2	2000ms	131072kb
10-3	2000ms	131072kb