P3497 [POI 2010] KOL-Railway

**译自 POI 2010 Stage 1.「[Kolej](https://szkopul.edu.pl/problemset/problem/TJVrS_hRC8W5Q6ZBW6mETAIm/site/?key=statement)」** 一个铁路包含两个侧线 $1$ 和 $2$ ，左边由 $A$ 进入，右边由 $B$ 出去（如下图所示）。  有 $n$ 个车厢在通道 $A$ 上，编号为 $1$ 到 $n$ ，它们按照 $a_1,a_2,\cdots ,a_n$ 的顺序进入侧线，想要按照 $1,2,\cdots ,n$ 的顺序从通道 $B$ 出去。 他们可以从 $A$ 到 $1$ 或 $2$ ，然后经过一系列转移从 $B$ 出去（不用考虑容量问题）。求是否能够做到，如果可以，请找出一种方案。

第一行一个正整数 $n$ 。 第二行 $n$ 个空格隔开的正整数 $a_1,a_2,\cdots a_n$ 。

第一行一个字符串，如果能够做到，输出 ```TAK``` ，否则输出 ```NIE``` 。 若能做到，第二行 $n$ 个空格隔开的正整数，表示每个车厢进入的侧线编号。 如果有多解，输出任意一种。 翻译来自于 [LibreOJ](https://loj.ac/p/2448)。

对于 $100\%$ 的数据，有 $n \le 1 \times 10^5$。 Translated by Diamond_duke，来源 LOJ。