파일 업로드

라인 댄스

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

매년 봄마다 열리는 화려한 라인 댄스 파티에서 남자들과 여자들은 댄스 중에 서로 인사를 합니다. 

정상적으로 인사를 하는 한 쌍의 남녀들은 마치 이렇게 보입니다: '><'. 

때로는 인사하는 두 남녀 사이로 또 다른 한 쌍의 남녀가 끼어들기도 합니다: '> >< <'.

실제로, 더 많은 수의 사람이 혼합되어 이렇게 보일 때가 있습니다: '> >< < ><' (오른쪽에 두 번째로 인사를 하는 사람의 집합이 포함되어 있습니다). 복잡해 보이는 정렬도 알고보면 완벽하게 정상적인 라인 댄스 형태일 수 있습니다:

              > > > >< < >< < >< >< >< <

              | | | -- | -- | -- -- -- |
              | | ------    |          |
              | -------------          |
              --------------------------

행사 주최자인 상철은 종종 파트너를 잃은 여자가 그룹에 끼어들어 균형을 깨뜨리는 것을 발견했습니다.: '> >< < <><'. 

이는 엄격히 금지된 행위이며, 상철은 이를 막고 싶어합니다.

상철은 최대 500명의 사람들이 참여하는 라인 댄스의 cctv 기록을 복사한 후, 라인 댄스의 균형이 맞는지 (즉, 모든 사람들이 적어도 한 가지 방법으로 한 쌍씩 짝을 이루어 댄스를 추는지) 알고 싶어합니다.

각자 어떤 사람에게 인사를 했는지 확인하기 위해 공백을 제외하고 방향만을 복사하여 균형이 깨진 라인 댄스의 예시를 다음과 같이 표현했습니다. 예: '>><<<><'. 

여러분에게 라인 댄스의 규칙이 잘 지켜졌는지 프로그램을 작성하라는 상철의 요청이 있습니다.

 

상철에게는 N (1 <= N <= 1,000)개의 패턴의 cctv 기록 P_i가 있으며, 이는 길이가 다른 K_i (1 <= K_i <= 200)개의 문자 '>'와 '<'로 구성되어 있습니다. 그 패턴들이 제대로 인사하고 있는 사람의 쌍을 포함하고 있으면 'legal'를, 그렇지 않으면 'illegal'을 출력합니다.

💻 입력
  • 첫 번째 줄 : 하나의 정수 N
  • 두 번째 줄부터 N+1 번째 줄 : i 번째 줄은 K 문자 '>'와 '<'의 문자열과 함께 뒤따르는 정수를 포함합니다: K_i와 P_i
🖨️ 출력
  • 첫 번째 줄부터 N 번째 줄 : i 번째 줄 입력은 규칙을 잘 지킨 라인 댄스 구성을 가지고 있는지에 따라 'legal'이나 'illegal'이라는 단어를 포함합니다.(따옴표 없이)

💻 예제 입력 1
2
6 >><<><
4 ><<>
🖨️ 예제 출력 1
legal
illegal

출처: USACO 2011 February Bronze 1