그룹 단어 복원

시간 제한2초메모리 제한128 MB

요약
주어진 조각들을 모두 사용해 각 글자가 하나의 블록만 이루는 원래의 그룹 단어를 복원하거나 불가능한 경우와 여러 개 가능한 경우를 구분합니다.
난이도

보통10점 중 7점

유형
그래프, 문자열, DFS, 그리디
정답자
아직 제출이 없습니다

문제

어떤 단어에서 같은 알파벳이 나타나는 모든 위치가 하나의 연속된 구간을 이루면 그 단어를 그룹 단어라고 한다. 예를 들어 aabbbcc는 그룹 단어이고, abca는 a가 두 구간으로 나뉘므로 그룹 단어가 아니다.

하나의 그룹 단어를 여러 조각으로 자른 뒤, 그 조각들이 임의의 순서로 주어진다. 모든 조각을 정확히 한 번씩 이어 붙여 만들 수 있는 원래 그룹 단어를 찾아라.

입력

첫째 줄에 조각의 개수 N이 주어진다. N은 50 이하의 자연수이다.

둘째 줄부터 N개의 줄에 각 조각이 하나씩 주어진다. 각 조각은 길이가 20 이하인 알파벳 소문자 문자열이다.

출력

가능한 원래 그룹 단어가 정확히 하나라면 그 단어를 출력한다.

가능한 단어가 여러 개라면 -_-를 출력한다. 어떤 순서로도 그룹 단어를 만들 수 없다면 gg를 출력한다.

예제6

  1. 예제 1

    입력
    2
    te
    st
    
    예상 출력
    stte
    
  2. 예제 2

    입력
    3
    aaa
    a
    aa
    
    예상 출력
    aaaaaa
    
  3. 예제 3

    입력
    2
    ab
    bba
    
    예상 출력
    gg
    
  4. 예제 4

    입력
    3
    te
    s
    t
    
    예상 출력
    -_-
    
  5. 예제 5

    입력
    4
    orr
    rd
    woo
    www
    
    예상 출력
    wwwwooorrrd
    
  6. 예제 6

    입력
    1
    abcb
    
    예상 출력
    gg