필승 전략

원숭이와 멍멍이가 보드게임을 한다. 보드에는 알파벳 소문자로 이름 붙은 $n$개 위치가 있고, 게임말로 현재 위치를 표시한다. 매 라운드는 두 단계다.

1. 원숭이가 선택지 집합 하나를 고른다. 선택지는 멍멍이가 이동할 수 있는 위치들의 집합이다.
2. 멍멍이는 그 집합 안에서 위치 하나를 골라 게임말을 옮긴다.

시작 전 원숭이는 끝 위치, 멍멍이는 시작 위치를 각각 정한다. 원숭이는 게임말이 끝 위치에 도달하면 승리한다. 매 라운드 끝에 원숭이가 멍멍이에게 돈을 주므로, 원숭이가 이기지 못하면 패가망신한다.

둘 모두 최적 전략으로 플레이할 때, 모든 시작 위치 $p$와 끝 위치 $q$에 대해 원숭이가 이기는 최소 라운드 수를 구한다. 이길 수 없으면 $-1$이다.

첫 줄에 위치 개수 $n$ ($1 \le n \le 25$)이 주어진다. 위치 이름은 알파벳 소문자 앞 $n$개를 사용한다.

다음 $n$줄은 위치 순서대로 정보가 주어진다. 각 줄은 선택지 개수 $m$ ($1 \le m < 2n$)과 $m$개의 문자열로 이루어진다. 문자열은 선택지를 나타내고, 멍멍이가 고를 수 있는 위치들을 알파벳 순으로 담는다.

위치 순서대로 $n$줄을 출력한다. $i$번째 줄에는 시작 위치 $i$에서 끝 위치 $j$로 이기는 최소 라운드 수를 공백으로 구분하여 출력한다. 이길 수 없으면 $-1$을 출력한다.