[Poi2010]Railway

时间限制:10s      空间限制:259MB

题目描述

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

有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)

提示

没有写明提示


题目来源

没有写明来源