해밍 경로 찾기

길이가 같은 두 이진 코드의 해밍 거리는 같은 위치에서 값이 다른 비트의 개수입니다.

서로 다른 N개의 이진 코드가 주어지며, 모든 코드의 길이는 K입니다. 코드는 입력된 순서대로 1번부터 N번까지 번호가 붙습니다.

해밍 경로는 나열된 코드 번호들에서 이웃한 두 코드의 해밍 거리가 항상 1인 경로입니다.

서로 다른 두 코드 번호 A와 B가 주어질 때, A에서 B로 가는 가장 짧은 해밍 경로를 구하세요.

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어집니다(3 <= N <= 1,000, 2 <= K <= 30).

둘째 줄부터 N개의 줄에는 각 줄마다 길이가 K인 이진 코드가 하나씩 공백 없이 주어집니다. 모든 코드는 서로 다르며, 입력된 순서대로 1번부터 N번까지 번호가 붙습니다.

마지막 줄에는 해밍 경로를 찾을 서로 다른 두 코드 번호 A와 B가 주어집니다.

두 코드 사이에 해밍 경로가 존재하면, A부터 B까지 가는 가장 짧은 경로의 코드 번호들을 공백 하나로 구분해 출력합니다.

가장 짧은 경로가 여러 개라면 그중 하나만 출력해도 됩니다. 경로가 존재하지 않으면 -1을 출력합니다.