LABIRIN

 

Harry Potter sedang terjebak dalam suatu labirin (labirynth) bawah tanah yang berisi bom waktu. Dalam labirin terdapat sejumlah ruangan dengan koridor-koridor yang menghubungkannya. Setiap koridor hanya menghubungkan tepat dua ruangan yang berbeda dan setiap pasang ruangan oleh satu koridor atau tidak sama sekali. Ruang-ruang itu bisa berada dalam salah satu dari dua status: terkunci atau tak terkunci. Seseorang tidak bisa masuk ke dalam ruang yang tekunci, tapi ia bisa keluar dari ruangan yang terkunci itu. Sementara seseorang bisa keluar masuk ruang tak terkunci.

Di beberapa ruang terdapat tombol yang apabila ditekan akan mengubah status sejumlah ruang. Misalnya, ruang yang terkunci menjadi tidak terkunci dan sebaliknya ruang yang tak terkunci menjadi terkunci. Tentu saja jika Harry Potter berada di dalam ruangan yang memiliki tombol, ia tidak harus menekannya. Ia baru menekan manakala ia memerlukannya.

Salah satu ruang terdapat tangga untuk naik ke atas. Tuliskan suatu program dengan nama LABIRIN.PAS yang dapat membantu Harry Potter yang berada dalam salah satu ruang menemukan ruang yang berisi tangga naik ke atas itu termasuk tombol-tombol mana yang harus ditekan. Karena dikejar waktu program harus menemukan jumlah koridor yang harus dilalui Harry Potter, yang mungkin disertai dengan menekan tombol-tombol di ruangan tertentu ia sempat berada.

Masukan berisi deskripsi ruangan serta koridor-koridor dalam labirin tersebut, ruangan saat awal Harry Potter berada, dan daftar sejumlah tombol serta masing-masing ruangan yang statusnya berubah jika tombol tersebut ditekan.

 

Format Masukan

 

Masukan adalah file teks bernama LABIRIN.IN dengan format sebagai berikut. Baris pertama dari file masukan berisi dua integer yaitu N, yang menyatakan jumlah total kamar (1 ≤ N ≤ 100), dan S, yang menyatakan jumlah tombol (jumlah kamar yang berisikan tombol) (1 ≤ S ≤ 8). Tombol-tombol terlekat pad kamar-kamar bernomor 1 sampai S.

N baris berikutnya berisi deskripsi setiap kamar. Nomor kamar i pada baris ke (i+1). Pada setiap baris tersebut jika dimulai dengan 0 menandakan bahwa pada mulanya kamar tbs tak terkunci atau jika dimulai dengan 1 menandakan pada mulanya kamar ybs terkunci. Setelah spasi terdapat bilangan integer K, yang menyatakan jumlah kamar yang berhubungan dengan kamar ybs melalui koridor-koridor. Masih dalam baris yang sama, setelah satu spasi setelah terdapat K bilangan yang menyatakan nomor-nomor kamar tsb dengan penulisan yang dipisahkan spasi.

Dalam S baris berikutnya terdapat tombol-tombol, dari kamar pertama hingga kamar ke S.

Setiap dari baris-baris tsb dimulai dengan bilangan integer L, yang menyatakan jumlah kamar yang akan berubah jika tombol ditekan. Setelah spasi, berikutnya adalah L integer yang masing-masing menyatakan nomor-nomor kamar ybs yang masng-masing terpisahkan satu spasi.

Baris terakhir berisi dua bilangan A dan B; A adalah nomor kamar Harry Potter saat ini berada dan B nomor kamar yang berisi tangga naik ke atas.

 

Format Keluaran

 

Keluaran adalah file LABIRIN.OUT yang hanya berisi satu bilangan integer yang menyatakan jumlah minimal koridor yang harus dilalui untuk mencapai ruangan bertangga.

Note: Setiap data test dijamin selalu memiliki solusi, artinya dari ruang A selalu ada jalan untuk mencapai ruang B.

 

Contoh

 

LABIRIN.IN

4 1

0 1 3

1 2 3 4

0 2 1 2

0 1 2

1 2

3 4

 

LABIRIN.OUT

4

 

 

LABIRIN.IN

5 2

0 2 2 5

1 2 1 3

0 2 2 4

1 2 3 5

0 2 1 4

2 2 4

2 3 4

5 3

 

LABIRIN.OUT

3

 

 

LABIRIN.IN

6 2

0 2 6 5

1 2 4 6

0 1 4

1 3 2 5 3

0 3 1 4 6

0 3 1 5 2

3 2 5 3

1 4

6 3

 

LABIRIN.OUT

8