레이팅 미적용Alice와 Bob이 보드게임을 하고 있다. 보드는 a, b, c, d, . . .로 이름 붙은 위치들로 나뉘어 있고, 플레이어들은 말 하나로 현재 위치를 표시한다. 게임의 각 라운드는 두 단계로 이루어진다. 1. Alice가 선택한다. 현재 위치에 따라 그녀에게는 서로 다른 선택지가 있으며, 각 선택지는 위치들의 집합이다. Alice는 사용할 수 있는 위치 집합들 중 하나의 집합 \(S\)를 고른다. 2. Bob이 선택한다. 그의 선택은 1단계에서 Alice가 고른 집합 \(S\)에 속한 위치 \(p\) 하나이다. Bob은 말을 위치 \(p\)로 옮기고, 그곳이 다음 라운드가 시작되는 위치가 된다. 첫 라운드에 앞서 각 플레이어는 독립적으로 위치 하나를 고르고 게임 시작 시 공개한다. Bob의 위치가 게임이 시작되는 곳이다. Alice는 Bob이 말을 자신이 고른 위치로 옮기도록 강제할 수 있으면 게임에서 이긴다. 재미를 위해 그들은 Bob이 지면 Alice에게 일정 금액을 지불하되, Alice는 매 라운드가 끝날 때마다 Bob에게 일정 금액을 지불하기로 했다. 이제 게임은 Alice의 위치에 도달하거나 Alice의 돈이 떨어지면 끝난다. Alice와 Bob 모두 최적으로 플레이한다. Alice는 가능하다면 항상 게임 승리로 이어지는 선택지를 고르고, Bob은 항상 Alice의 승리를 막으려 한다. 가능한 모든 시작 위치와 목표 위치에 대해, Alice는 자신이 게임에서 이길 수 있는지, 이길 수 있다면 몇 라운드가 걸리는지 알고 싶어 한다.
입력은 하나의 테스트 케이스로 이루어져 있다. 첫 줄에는 위치의 수 \(n\) (\(1 \le n \le 25\))이 주어진다. \(n\)개의 위치는 영어 알파벳 소문자 중 앞에서부터 \(n\)개의 글자로 이름 붙는다. 테스트 케이스의 나머지는 위치 \(p\)마다 한 줄씩, 알파벳 순서로 \(n\)개의 줄로 이루어진다. 위치 \(p\)의 줄에는 위치 \(p\)에서 Alice가 쓸 수 있는 선택지들이 담겨 있다. 줄은 선택지의 수 \(m\) (\(1 \le m < 2^{n}\))으로 시작하고, 이어서 선택지마다 하나씩 서로 다른 문자열 \(m\)개가 온다. 각 문자열에는 Alice가 그 선택지를 골랐을 때 Bob이 쓸 수 있는 위치들이 담겨 있다. 문자열은 적어도 1글자이고, (유효한 보드 위치에 대응하는) 글자들은 알파벳 순서이며, 중복되는 글자는 없다. 테스트 케이스의 선택지 총수는 최대 \(10^{6}\)이다.
알파벳 순서로 각 위치 \(p\)마다 한 줄을 출력한다. 그 줄에는 알파벳 순서의 각 위치 \(q\)에 대해, 위치 \(p\)에서 게임을 시작할 때 Alice가 위치 \(q\)에 도달함을 보장할 수 있는 최소 라운드 수를 출력하고, Alice가 \(p\)에서 \(q\)에 도달함을 보장할 수 없으면 −1(\(or - 1\))을 출력한다.
2
2 ab b
1 b
0 1
-1 0
3
1 b
2 b a
2 ab ac
0 1 -1
1 0 -1
2 2 0