{"code":"tkpc07frog","name":"Huy Nhảy","description":"Bảo Huy là chú ếch đẹp trai nhất đầm sen ITK19. Đầm sen này được chia thành một bảng ô vuông gồm $M$ hàng (đánh số từ trên xuống dưới) và $N$ cột (đánh số từ trái qua phải). Ta quy ước ô nằm ở giao điểm của hàng $i$ và cột $j$ là ô $(i, j)$. Một số ô trong đầm có chứa một lá sen nổi (ký hiệu `o`) để Huy có thể nhảy lên, các ô còn lại có 100% bề mặt là nước (ký hiệu là `.`). Huy cần nhảy từ ô có ký tự `S` đến ô có ký tự `T` (hai ô này đều mặc định chứa một lá sen) theo quy tắc: ở mỗi bước anh chỉ có thể nhảy từ ô hiện tại đến một ô chứa lá sen trên cùng hàng hoặc cùng cột. [user:CaiWinDao] muốn bỏ đi một số lá sen trong đầm (trừ hai lá tại `S` và `T`) để Huy không còn có thể nhảy từ `S` đến `T` nữa. Các bạn hãy lập trình giúp [user:CaiWinDao] xác định số lá sen ít nhất cần bỏ đi nhé!\r\n\r\n

Input

\r\n\r\n- Dòng đầu hai số nguyên dương $M$ và $N$ $(2\\leq M, N\\leq 100)$.\r\n\r\n- $M$ dòng sau, mỗi dòng chứa $N$ ký tự mô tả đầm sen.\r\n\r\n

Output

\r\n\r\n- Một số nguyên là số lượng lá sen ít nhất cần bỏ để Huy không thể nhảy từ `S` đến `T`. Nếu không tìm được phương án thỏa mãn thì in ra $-1$. \r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 3\r\n S.o\r\n .o.\r\n o.T\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n [user:CaiWinDao] cần bỏ đi lá sen ở góc trên bên phải và góc dưới bên trái.\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 4\r\n S...\r\n .oo.\r\n ...T\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 0\r\n ```\r\n \r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4 3\r\n .S.\r\n .o.\r\n .o.\r\n .T.\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n -1\r\n ```\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 10 10\r\n .o...o..o.\r\n ....o.....\r\n ....oo.oo.\r\n ..oooo..o.\r\n ....oo....\r\n ..o..o....\r\n o..o....So\r\n o....T....\r\n ....o.....\r\n ........oo\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 5\r\n ```","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}