끝말잇기

비밀의 문 가운데 일부에는 아주 흥미로운 단어 퍼즐이 걸려 있다. 고고학 발굴대는 문을 열기 위해 이 퍼즐을 반드시 풀어야 한다. 문을 열 다른 방법이 없으므로, 이 퍼즐은 우리에게 매우 중요하다.

각 문에는 수많은 자석판이 붙어 있고, 판마다 하나의 단어가 적혀 있다. 이 판들을 한 줄로 배열하되, 각 단어의 첫 글자가 바로 앞 단어의 마지막 글자와 같도록 이어 붙여야 한다. 예를 들어 단어 ac*m* 뒤에는 단어 *m*otorola가 올 수 있다. 단어 목록을 읽어 들여, 주어진 규칙에 따라 모든 판을 하나의 순서로 배열해 문을 열 수 있는지 판정하는 프로그램을 작성하라.

입력은 $T$개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 판의 개수를 나타내는 정수 $N$이 주어진다 ($1 \le N \le 100000$). 이어서 정확히 $N$개의 줄이 오며, 각 줄에는 단어가 하나씩 적혀 있다. 각 단어는 최소 2글자, 최대 1000글자로 이루어지며, 모두 소문자 알파벳 a부터 z까지만 사용한다. 같은 단어가 목록에 여러 번 나타날 수도 있다.

각 테스트 케이스에 대해, 모든 판을 한 줄로 배열하여 각 단어의 첫 글자가 바로 앞 단어의 마지막 글자와 같게 만들 수 있는지 판정하라. 목록의 모든 판을 각각 정확히 한 번씩 사용해야 하며, 여러 번 등장하는 단어는 등장한 횟수만큼 사용해야 한다.

그런 배열이 존재하면 Ordering is possible. 를 출력하고, 그렇지 않으면 The door cannot be opened. 를 출력한다.