limho0305   2년 전

N개의 스테이션이 있는 조립 라인을 가정해봅시다. 각각의 스테이션에 대해 작업자들은 제품에 특정한 행동을 할 것인데 이것은 다음 혹은 이전 스테이션과 동일한 작업일 수 있습니다. 같은 종류의 스테이션끼리의 순서는 딱히 중요하지는 않지만 다음과 같은 순서대로 나오긴 해야됩니다. 제품이 한쪽(좌 또는 우)에서 투입되면 반대쪽(우 또는 좌)로 나오게 되는데 이 제품이 지나간 스테이션 종류의 순서가 반대로 투입했을때도 유지되게 해야됩니다. 당신의 일은 이러한 규칙을 만족하게끔 기존에 존재하는 조립 라인을 재구성하는 것입니다. 여러번의 "스테이션 스왑" 행동을 통해 이 목적을 실현할 수 있으나 이 행동은 서로 붙어있는 두 스테이션만 서로 위치를 바꿀 수 있습니다.

입력

첫번째 줄에 테스트 케이스의 수 N이 주어집니다.

각각의 케이스마다 100개 이하의 문자로 이루어진 문자열이 주어지며 각 문자는 스테이션의 종류(이름)을 뜻합니다.

출력

각각의 테스트 케이스마다 조건에 부합하게 재구성하기 위해 필요한 최소한의 "스테이션 스왑"행동의 횟수 또는 불가능하다면 "Impossible"을 출력하세요.

예를 들어 총 3종류의 스테이션 2, a, D를 가지고 있고 처음엔 "2a2aD"로 배열되어있었다고 하면, 총 3번의 "스테이션 스왑"으로 조건에 만족하게 할 수 있습니다.

* "aD"를 스왑해 "2a2Da"로 만듭니다.

* "2D"를 스왑해 "2aD2a"로 만듭니다.

* "2a"를 스왑해 "2aDa2"로 만듭니다.

댓글을 작성하려면 로그인해야 합니다.