Description

There are $N$ items and $L$ drawers. Each drawer can hold only $1$ item. Each item can be placed into drawer $A_i$ or $B_i$.

The rules for placing an item are as follows (performed in order: once condition $1$ is satisfied, execute it immediately and do not execute condition $2$; only if condition $1$ is not satisfied do you check condition $2$, and so on):

• $1.$ If drawer $A_i$ is empty, put this item into drawer $A_i$.

• $2.$ If drawer $B_i$ is empty, put this item into drawer $B_i$.

• $3.$ Move the item currently in drawer $A_i$ to its other drawer. If that drawer is also full, move the item in that drawer to its other drawer, and so on, until you succeed or return to a drawer you have encountered before. If you succeed, put this item into that drawer.

• $4.$ Move the item currently in drawer $B_i$ to its other drawer. If that drawer is also full, move the item in that drawer to its other drawer, and so on, until you succeed or return to a drawer you have encountered before. If you succeed, put this item into that drawer.

• $5.$ Throw away this item.

For each given item, determine which items will be kept and which will be thrown away.

Input Format

The first line contains two integers $N$ and $L$, representing the number of items and the number of drawers.

The next $N$ lines each contain two integers $A_i$ and $B_i$, meaning that item $i$ can be stored in these two drawers.

Output Format

Output $N$ lines, each containing one string.

If the item is successfully stored, output LADICA.

If the item is thrown away, output SMECE.

5 3
1 2
1 3
1 2
1 3
1 2 

LADICA
LADICA
LADICA
SMECE
SMECE 

9 10
1 2
3 4
5 6
7 8
9 10
2 3
1 5
8 2
7 9 

LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA

Hint

[Sample Explanation #1]

Item $1$ is placed into drawer $1$, item $2$ into drawer $3$, item $3$ into drawer $2$, and items $4$ and $5$ have nowhere to go.

[Sample Explanation #2]

Item $1$ is placed into drawer $1$, item $2$ into drawer $3$, item $3$ into drawer $5$, item $4$ into drawer $7$, item $5$ into drawer $9$, item $6$ into drawer $2$, and item $8$ into drawer $8$.

Both drawers for item $7$ are full. Move item $1$ in drawer $1$ to drawer $2$, move item $6$ in drawer $2$ to drawer $3$, move item $2$ in drawer $3$ to drawer $4$. Drawer $4$ is empty, so the insertion succeeds.

Both drawers for item $9$ are full. Move item $4$ in drawer $7$ to drawer $8$, move item $8$ in drawer $8$ to drawer $2$, move item $1$ in drawer $2$ to drawer $1$, move item $7$ in drawer $1$ to drawer $5$, move item $3$ in drawer $5$ to drawer $6$. Drawer $6$ is empty, so the insertion succeeds.

[Constraints]

For $50\%$ of the testdata, $1\le N,L\le 2000$.

For $100\%$ of the testdata, $1\le N,L\le 3\times 10^5$, $1\le A_i,B_i\le L$.

[Notes]

The score of this problem follows the original COCI setting, with a full score of $160$.

Translated from COCI2013_2014 CONTEST #5 T6 LADICE.

Translated by ChatGPT 5