1s, 64MB

Kwik adalah bebek Pak Dengklek yang senang menonton TV. Salah satu film favoritnya adalah serial “The Indiana Duck”. Serial ini mengisahkan seekor bebek yang bekerja sebagai arkeologi dan menemukan harta karun historis di seluruh dunia. Indiana Duck terkenal dengan atribut legendarisnya berupa topi koboi dan cambuk untuk membela diri dari serangan musuh.

Pada suatu hari, Kwik menemukan peta harta karun dalam kotak kecil di salah satu sudut gudang Pak Dengklek. Dalam peta itu tertulis jika seseorang mendaki turun melalui sumur tua di belakang gudang, maka ia akan menemui gua raksasa berukuran R × C dengan lautan magma di bawahnya. Dari dasar lautan magma tersebut menyembul beberapa bongkahan batu keras yang dapat digunakan sebagai pijakan. Pada salah satu bongkahan batu terdapat harta karun yang sudah dijaga selama beberapa generasi keluarga Dengklek. Kwik sangat senang karena dia bisa berlagak meniru Indiana Duck tokoh idolanya.

Satu-satunya cara untuk berpindah dari suatu bongkahan batu ke bongkahan batu lainnya adalah dengan melompat (Kwik tidak boleh menyentuh lautan magma jika ingin kembali hidup-hidup). Selama berada dalam suatu bongkahan batu, Kwik dapat menjelajahi bongkahan batu tersebut tanpa perlu melompat (misalnya, untuk berpindah ke sisi lain kemudian baru melompat). 2 petak batu akan membentuk sebuah bongkahan batu besar jika kedua petak batu tersebut berbagi sisi.

Karena Kwik masih kecil, dia tidak dapat melakukan gerakan yang sulit. Kwik hanya bisa melompat untuk menyeberangi lautan magma secara garis lurus (tidak dapat berbelok di udara). Kwik juga hanya dapat melompat ke arah utara, timur, selatan, atau barat. Karena perjalanan panjang, Kwik akan menghemat tenaganya dan akan selalu mendarat di bongkahan batu terdekat yang ditemuinya di arah lompatan.

Kwik berencana mendapatkan harta karun yang disebutkan dalam peta Kwik pun menceritakan rencana hebatnya kepada Anda dan meminta agar Anda tidak melapor ke Pak Dengklek. Anda sangat khawatir dengan keselamatan Kwik, namun Anda juga tidak bisa menemani Kwik dalam petualangannya karena Anda tidak ingin ketinggalan acara “Duck’s Got Talent”. Karena itu Anda hendak membantu Kwik dengan menentukan berapa lompatan minimal yang harus dilakukan Kwik agar dapat sampai ke harta karun (tentunya, semakin sedikit melompat akan menghemat energi Kwik dan menjamin keselamatannya).

Format Masukan

Pada awalnya, program Anda akan menerima label kasus uji. Label kasus uji berisi sebuah string yang dijelaskan sebagai berikut:

Panjang string tersebut adalah banyaknya subsoal ditambah satu.
Digit pertama dari label adalah karakter ke-0, digit kedua dari label adalah karakter ke-1, dan seterusnya.
Karakter ke-0 akan berisi 0 jika kasus uji tersebut merupakan contoh kasus uji, atau berisi '.' jika bukan.
Untuk setiap nilai i di antara 1 hingga banyaknya subsoal, berlaku:
jika kasus uji tersebut memenuhi batasan subsoal ke-i, maka karakter ke-i berisi i, atau
jika kasus uji tersebut tidak memenuhi batasan subsoal ke-i, maka karakter ke-i berisi karakter '.'
Sebagai contoh apabila label sebuah kasus uji sebuah soal adalah 0..345, maka:

Soal tersebut memiliki 5 buah subsoal,
Kasus uji tersebut merupakan contoh kasus uji, dan
Kasus uji tesebut memenuhi batasan subsoal ke-3, ke-4, dan ke-5.
Baris kedua dalam berkas masukan berisi 2 buah bilangan R dan C yang dipisahkan oleh tepat sebuah spasi. R baris berikutnya berisi C buah karakter yang menyatakan konfigurasi petak batu dan lokasi harta karun sesuai deskripsi dalam peta. Sebuah petak dalam gua raksasa tersebut hanya dapat berupa salah satu dari kemungkinan karakter di bawah ini.

‘#’ : petak tersebut merupakan petak batu yang bisa diinjak.
‘.’ : petak tersebut merupakan lautan magma yang tidak boleh diinjak.
‘S’ : petak ini merupakan bagian akhir dari tangga pada sumur, atau dengan kata lain tempat Kwik memulai petualangannya. Petak ini pasti merupakan bagian dari petak batu yang bisa diinjak.
‘T’ : petak ini tempat harta karun yang dimaksud. Petak ini pasti merupakan bagian dari petak batu yang diinjak.
Format Keluaran

Cetak sebuah bilangan dalam 1 baris yang menyatakan berapa banyak lompatan paling sedikit yang harus dilakukan Kwik agar dapat sampai ke petak harta karun. Cetak -1 jika Kwik tidak akan pernah menemukan harta karun.

Contoh Masukan

0....56
7 7
#....#T
#..#...
..##..#
...#..#
.#.#..#
.#..S..
.#..#..
Contoh Keluaran

4

Subtask

Pada semua subsoal, berlaku:

• Banyaknya bongkahan batu tidak melebihi 1.000.

Subsoal 1 (11 poin)

• R = 12
• C = 12
• Semua bongkahan batu terdiri dari tepat satu petak batu.
• Berkas kasus uji bisa diunduh di sini.

Subsoal 2 (8 poin)

• R = 12
• C = 12
• Berkas kasus uji bisa diunduh di sini.

Subsoal 3 (18 poin)

• 1 ? R, C ? 100
• Semua bongkahan batu terdiri dari tepat satu petak batu.

Subsoal 4 (21 poin)

• 1 ? R, C ? 100
• Semua bongkahan batu berbentuk persegi panjang.

Subsoal 5 (26 poin)

• 1 ? R, C ? 100

Subsoal 6 (16 poin)

• 1 ? R, C ? 1.000