길이가 같은 두 개의 이진수 코드w_1과w_2가 있다고 하자.

이 두 코드 사이의 해밍 거리(Hamming distance)는

w_1과w_2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다.

예를 들어, w_1=010010, w_2 = 011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 해밍 거리는 2이다.

KOI 연구소는 특정 암호문에서 사용되는 총 N개의 이진 코드를 가지고 있다. 각 코드의 길이는 K로 일정하다.

연구소는 이 코드들에 대해 여러 가지 특징을 분석하고 있다. 예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다고 하자.

w_1=000, w_2=111, w_3=010, w_4=110, w_5=001

두 코드 w_i와 w_j 사이의 해밍 거리를 hd(w_i, w_j)로 표현한다.

그러면, hd(w_1, w_2) = 3, hd(w_1, w_3) = 1, hd(w_1, w_4) = 2, hd(w_1, w_5) = 1 이다.

당신은 이진 코드들에 대해 해밍 경로(Hamming path)를 찾고자한다.

해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다.

위의 예에서 (w_1, w_3, w_4는 길이가 3인 해밍 경로이지만, (w_1, w_5, w_2)는 해밍 경로가 아니다.

두 코드 사이에 해밍 경로가 여러 개가 있을 경우 가장 짧은 경로를 찾고자 한다.

이 문제는 1번 코드에서부터 질의로 주어진 여러 개의 코드까지의 해밍 경로를 각각 구하는 프로그램을 작성하는 것이다.

해밍 경로 timer 2초 memory 128MB

해밍 경로 2초 128MB