In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
King Byteasar faces a serious matter. Two competing trade organisations, The Tailors Guild and The Sewers Guild asked, at the same time, for permissions to open their offices in each town of the kingdom.
There are towns in Byteotia. Some of them are connected with bidirectional roads. Each of the guilds postulate that every town should:
Two integers, and (, ), are given in the first line of the standard input. These denote the number of towns and roads in Byteotia, respectively. The towns are numbered from to . Then the roads are given as follows: the input line no. describes the -th road; it holds the numbers and (, ), denoting that the -th road connects the towns and . Every pair of towns is (directly) connected by at most one road. The roads do not cross - meeting only in towns - but may lead through tunnels and overpasses.
Your program should print out one word in the first line of the standard output: TAK (yes in Polish) - if the offices can be placed in towns according to these rules, or NIE (no in Polish) - in the opposite case. If the answers is TAK, then the following lines should give an exemplary placement of the offices. Thus the line no. should hold:
For the input data:
7 8 1 2 3 4 5 4 6 4 7 4 5 6 5 7 6 7
the correct result is:
TAK K S K S K K N
The towns in which an office of The Tailors Guild should open are marked with circles, whereas those in which an office of The Sewers Guild should open are marked with rhombi.
Task author: Marcin Pilipczuk.