Bulls and Cows

Bulls and Cows는 두 사람이 하는 게임으로, 한 명은 출제자(codemaker), 다른 한 명은 추측자(codebreaker)이다. 출제자는 서로 모두 다른 $K$개의 십진수 숫자로 이루어진 비밀 코드를 정한다(맨 앞자리가 0이어도 된다). 추측자는 $K$자리 수를 불러 가며 이 코드를 알아내려 한다.

추측할 때마다 출제자는 두 가지 개수를 알려 준다.

• 불(Bulls) — 값과 위치가 모두 맞은 숫자의 개수.
• 카우(Cows) — 값은 코드에 들어 있지만 위치가 틀린 숫자의 개수.

예를 들어 비밀 코드가 1230이고 추측자가 1205를 불렀다면, 대답은 2 Bulls, 1 Cow이다.

한 게임의 모든 추측과 대답 기록이 주어질 때, 아직 가능한 코드가 몇 개인지와, 그중 수로서 가장 작은 코드가 무엇인지 구하라.

입력은 하나 이상의 게임 설명으로 이루어진다.

각 게임 설명은 정수 $K$ ($1 \le K \le 7$) 하나가 적힌 줄로 시작한다. $K$가 양수가 아니면 입력의 끝을 뜻한다.

양수인 $K$ 다음에는 0개 이상의 '추측-대답' 줄이 온다. 각 줄에는 하나 이상의 공백으로 구분된 $K+2$개의 정수가 있으며, 앞의 $K$개는 추측한 수의 각 자리 숫자, 그다음 정수는 불(Bulls)의 개수, 마지막 정수는 카우(Cows)의 개수이다. '추측-대답' 줄의 나열은 첫 번째 정수가 $-1$인 줄로 끝나며, 그 줄의 나머지 정수는 무시한다.

각 게임마다 다음과 같은 형식으로 정확히 한 줄을 출력한다.

N is one of M possible solutions.

여기서 $N$은 모든 추측과 대답에 부합하는 코드 중 수로서 가장 작은 것을(맨 앞의 0을 포함하여 $K$자리 숫자를 구분 기호 없이 이어서) 나타내고, $M$은 전체 기록에 부합하는 코드의 개수이다.