#1076. 2080. [Poi2010]Railway

2080. [Poi2010]Railway

#2080. [Poi2010]Railway

题目描述

一个铁路包含两个侧线1和2,右边由A进入,左边由B出去(看下面的图片)

image

有n个车厢在通道A上,编号为1到n,它们被安排按照要求的顺序(a1,a2,a3,a4....an)进入侧线,进去还要出来,它们要按照编号顺序(1,2,3,4,5。。。。n)从通道B出去。他们从A到1或2,然后经过一系列转移从B出去,不用考虑容量问题。

输入格式

输入:第一行一个整数n(1<=n<=100000)表示要转移的车厢总数,第二行为进入侧线的要求顺序a1.a2.a3.a4....an,由空格隔开。

输出格式

输出:如果可以按照编号顺序到通道B,则输出两行,第一行为TAK,第二行为n个由空格隔开的整数,表示每个车厢进入的侧线编号(1,2)。否则输出NIE。要求输出字典序最小的方案

样例

样例输入

[样例输入1]  

4  

1 3 4 2  

[样例输入2]  

4  

2 3 4 1

样例输出

[样例输出1]  

TAK  

1 1 2 1        (1号线进到侧线1,然后出来,3号进入侧线1,4号进入侧线2,2号进入侧线1,然后出来,接着3号出来,4号出来)  

[样例输出2]  

NIE            (不可能。。No)

数据范围与提示