화창한 어느 날 농부 존은 사악한 농부 마르크스의 소들에게 납치당했다. 농부 존은 그의 휴일을 망친 것보다 그의 소들이 안전하게 돌아가길 바란다.

소들은 농부 존의 N(3 ≤ N ≤ 200)개의 초원에 퍼져 있다. 헛간은 초원 1에 있다. 농장은 흥미로운 길 안내 시스템을 갖고 있다. 모든 초원 i에 M(1 ≤ N ≤ 200)개의 표시가 S_ij(1 ≤ S_ij ≤ N)개의 목적지가 S_i1, ... S_iM 식으로 적혀 있다. (M갈래로 뻗어진 갈림길을 생각하면 쉽다 - 역주) 각 표시는 다른 초원으로의 방향을 가리키지만 가끔 현재 위치를 가리키기도 한다.

농부 마르크스의 소들은 농부 존에게 단 한 개의 메시지를 그의 소들에게 전할 수 있게 한다. 농부 존은 어떤 소든지 헛간으로 보낼 수 있는 신호의 리스트를 만들어서 전하려고 한다.

소들의 위치가 주어지면 소들은 농부 존의 메시지를 따라서 이동한다. 소들이 두 번째 초원에 도착하면 소들은 농부 존의 두 번째 신호를 보고 움직인다. 소들은 메시지가 완료되거나 헛간에 도착할 때까지 이러한 작업을 반복한다.

모든 소들을 헛간으로 인도할 수 있는 5,000,000개 이하의 신호들을 찾는 게 목표이다.

여기 부적절한 예제가 있다.

         --초원 번호-- 
 　      1   2   3   4 
신호 1   4   4   1   3 
신호 2   1   3   2   4 
신호 3   4   2   3   1 

명령번호    신호번호 
   1            1 
   2            2 
   3            1 
   4            2 
   5            3 
   6            1 
   7            3 

시간    현위치    신호    다음 위치 
 1         1        1         4 
 2         4        2         4 (제자리) 
 3         4        1         3 
 4         3        2         2 
 5         2        3         2 (제자리) 
 6         2        1         4 
 7         4        3         1 (도착!) 

같은 원리로, 초원 2의 소는 [2]→4→4→3→2→2→4→1, 
    　　　  　 　 3의 소는 [3]→1→1→4→4→1→4→1, 
　  　　　  　 　 4의 소는 [4]→3→2→4→4→1→4→1 의 순서로 이동하여 모두 헛간에 들어가게 된다. 

• - 각 초원에 소들이 이동하게 될 다른 초원의 번호가 M개 적혀 있다. (M갈래길을 생각하면 된다)
• - 농장 곳곳에 흩어져 있는 소들은 농부 존의 메시지에 따라 움직인다. (M개의 갈림길 중에서 존이 명령한 길로 간다)
• - 모든 소를 헛간(초원 1)으로 보내는 것이 목표이다.

입력

정리하자면,

(초원의 수 N) (신호의 개수 M) 
(초원1의 첫 번째 신호) (초원2의 첫 번째 신호)... 
(초원1의 두 번째 신호) (초원2의 두 번째 신호)... 
(초원1의 세 번째 신호) (초원2의 세 번째 신호)... 

출력

입출력 예

입력 

4 3 
4 4 1 3 
1 3 2 4 
4 2 3 1 

출력 

1 
2 
1 
2 
3 
1 
3

출처:usaco FEB11 gold
special judge:august14
번역:abc