성재는 방 정리를 할 때 서랍장도 같이 정리하기로 마음먹었다. 성재는 방에 있던 N개의 물건을 L개의 서랍장에 담으려고 한다. 성재는 기억하기 쉽게 아래 방식으로 물건을 넣으려고 한다.

• 성재는 k번째 물건을 Ak번 서랍 또는 Bk번 서랍 중 한 곳에 넣어야 하며, 각 서랍에는 최대 한 개의 물건을 넣을 수 있다.
• 성재는 1번째 물건에서부터 차례대로 서랍에 넣는다.
• 성재가 k번째 물건을 넣을 때에는 다음과 같은 방법으로 물건을 넣는다.
  • 1) Ak번 서랍이 비어있다면 Ak번 서랍에 물건을 넣는다.
  • 2) Bk번 서랍이 비어있다면 Bk번 서랍에 물건을 넣는다.
  • 3) Ak번 서랍에 있던 물건을 다른 곳으로 넣는다. 만약 그곳에도 물건이 있다면 그곳에 있는 물건을 다른 곳으로 넣는다. 이 작업은 빈 서랍이 발견될 때까지 하며, 빈 서랍을 발견해서 물건들을 다른 곳으로 옮겼다면 k번 물건은 Ak번 서랍에 넣는다.
  • 4) Bk번 서랍에 있던 물건을 다른 곳으로 넣는다. 만약 그곳에도 물건이 있다면 그곳에 있는 물건을 다른 곳으로 넣는다. 이 작업은 빈 서랍이 발견될 때까지 하며, 빈 서랍을 발견해서 물건들을 다른 곳으로 옮겼다면 k번 물건은 Bk 번 서랍에 넣는다.
  • 5) 위의 네 방법을 모두 실패했다면, 물건을 버린다.

입력 형식

• 첫 번째 줄에는 물건의 수 N과 서랍장의 수 L이 주어진다. (1 ≤ N, L ≤ 300,000)
• 두 번째 줄에는 각 물건에 대해 Ak와 Bk가 주어진다. (1 ≤ Ak, Bk ≤ L, Ak ≠ Bk)

출력 형식

입력 예 1

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

출력 예 1

LADICA
LADICA
LADICA
SMECE
SMECE

입력 예 2

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

출력 예 2

LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA


입력 예 1 설명
첫 번째 물건은 1번째 규칙에 의해 1번 서랍에 들어가고, 두 번째 물건은 2번째 규칙에 의해 3번 서랍에 들어간다. 세 번째 물건은 2번째 규칙에 의해 2번 서랍에 들어간다.
이미 3개의 서랍이 꽉 찼기 때문에 4, 5번 물건은 버려진다.

입력 예 2 설명
첫 여섯 개의 물건은 각각 1, 3, 5, 7, 9, 2번 서랍에 들어간다.
7번째 물건은 3번 규칙에 의해 1번 서랍에 있던 물건을 2번 서랍에, 2번 서랍에 있던 물건을 3번 서랍에, 3번 서랍에 있던 물건을 4번 서랍에 넣으려고 할 것이다. 4번 서랍이 비었기 때문에 1, 6, 2번째 물건은 각각 2, 3, 4번 서랍으로 옮겨지고 7번째 물건은 1번 서랍에 들어간다.
8번째 물건은 8번 서랍에 들어간다.
9번째 물건은 3번 규칙에 의해 7번 서랍에 있던 물건을 8번 서랍에, 8번 서랍에 있던 물건을 2번 서랍에, 2번 서랍에 있던 물건을 1번 서랍에, 1번 서랍에 있던 물건을 5번 서랍에, 5번 서랍에 있던 물건을 6번 서랍에 넣으려고 할 것이다. 6번 서랍이 비었기 때문에 4, 8, 1, 7, 3번째 물건은 각각 8, 2, 1, 5, 6번 서랍으로 옮겨지고 9번째 물건은 7번 서랍에 들어간다.

Mirko stores the items in order from 1 to N using the first rule he can apply: 1. If the drawer Ai is empty, he stores the item i in that drawer 2. If the drawer Bi is empty, he stores the item i in that drawer 3. Try to move the item from Ai to its other drawer; if that one's filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item i in the drawer Ai . In case of failure, continue to next rule. 4. Try moving the item from Bi to its other drawer; if that one's filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item i in the drawer Bi . In case of failure, continue to next rule. 5. Give up and throw away the item i. For given pairs of drawers for each item, determine which items will be stored and which will be thrown away.

입력

출력

입출력 예

input 
 
5 3 
1 2 
1 3 
1 2 
1 3 
1 2 
 
output 
 
LADICA 
LADICA 
LADICA 
SMECE 
SMECE 
input 
 
9 10 
1 2 
3 4 
5 6 
7 8 
9 10 
2 3 
1 5 
8 2 
7 9 
 
output 
 
LADICA 
LADICA 
LADICA 
LADICA 
LADICA 
LADICA 
LADICA 
LADICA 
LADICA 

Clarification of the first example: The first item goes to drawer 1 by rule 1). The second item goes to 
drawer 3 by rule 2). The third item goes to drawer 2 by rule 2). 
For the fourth and fifth item, both drawers are already taken and cannot be emptied. 
Clarification of the second example: The first six items go into drawers 1, 3, 5, 7, 9, 2 (respectively), 
by rule 1). For the seventh item, applying the rule 3), we try to move the item in drawer 1 to drawer 2, 
the item in drawer 2 to drawer 3, the item in drawer 3 to drawer 4, which we succeed because the 
drawer is empty. 

The eighth item goes to drawer 8 which was empty from the beginning. 
For the ninth item, applying the rule 3), we try to move the item in drawer 7 to drawer 8, the item in 
drawer 8 to drawer 2, the item in drawer 2 to drawer 1, the item in drawer 1 to drawer 5, the item in 
drawer 5 to drawer 6, which we succeed because the drawer is empty

출처:/coci/2013-2014/contest5
번역:functionx