Souvenirs of Love

Time Limit: 5 Seconds    Memory Limit: 32768 KB
Special Judge

They sleep, and at length awake to the still reality of a winter morning. The snow lies warm as cotton or down upon the window sill; the broadened sash and frosted panes admit a dim and private light, which enhances the snug cheer within.

They silently unlock the windows, letting the drift fall in. They see the roofs stand under their snow burden. From the eaves and doorsteps hang stalactites of snow, and in the yard stand stalagmites covering some concealed core. The trees and shrubs rear white arms to the sky on every side; and where walls and fences are. They see fantastic forms stretching in frolic gambols across the dusky landscape, as if Nature had strewn her fresh designs over the fields by night as models for man's art.

"The result has been released." a shrill voice broke in Christopher's mind. He was just been told to have lung cancer and cardiopathy, and two more years left to him at most. Christopher unburdened himself to her just on the Xmas Eve. But since that... His last-ditch line of defense has been ripped up.

The birds flitted from branch to branch, a voice dripping with sweetness kept to be an aftertaste that lingers. Christopher picked up a piece of leaf; he knew that it was witness of the old-time friendship. Psychologist told him, he cannot be deadly hurt by any souvenir any more, or else, he'll be struck down by sudden death in worst case.

The wheels of life keep turning,
Spinning without control.
The wheels of the heart keep yearning,
For the sound of the singing soul;

And nights are full with weeping,
For seeds of the past we've sown,
But tomorrow is mine for the keeping,
Tomorrow the future's shown.

Psychologists have investigated out that the relationship between some souvenirs is the vital cause of Christopher's recalling(e.g. a pen and the cap of that pen), but Christopher hopes that he could see all of the survivors every day in his two study rooms, coz he's few glances of them in his remaining life.

Being Christopher's best friend, and one of the most famous coders in Micro Hard Software Company, you must help him! To predigest our problem:

Suppose Christopher has N souvenirs, before your programming, you'll be given a list of two relating souvenirs. For instance, souvenir A and B relate to each other. (Relationships are mutual.) Your aim is to put all of them in two study rooms, and for each one of them, the number of its relating souvenirs in the same room won't be larger than that in the other room.

Input

Input will contain several blocks (each for one test case). In each of the block, there'll be two integers in the first line - N and M. N is the number of souvenirs, and M is the quantity of relationships.

After that, there'll be M lines. In each, you'll get two integers or so. They denote the relationship of two souvenirs. No souvenir relates with itself.

Output

For each test case, you should output the possibility of plan in the first line - "TAK" for YES, and "NIE" for NO. If your output is "TAK", N bit numbers should continue on the following N lines. You could use - and only use - 0 or 1 to denote which room each should be put in your plan.

WARNING: No space line should be output, even between two neighboring test cases.

Sample Input

5 6
1 2
1 3
2 3
2 4
1 4
1 5

8 4
1 6
2 5
3 8
4 7

Sample Output

TAK
1
1
0
0
0
TAK
0
0
0
0
1
1
1
1

Submit

Source: JIANG, Yanyan's Contest #1