ग्रिड पर सबसे छोटा पथ (Shortest Path on a Grid)

एक भूलभुलैया, जो r पंक्तियों और c स्तंभों वाले ग्रिड के रूप में दर्शाया गया है, में आपको प्रारंभिक कोश (starting cell) से अंतिम कोश (end cell) तक जाने वाले सबसे छोटे रास्ते की लंबाई खोजनी है।

इस भूलभुलैया को निम्नलिखित तरीके से दर्शाया गया है:

• फ़्लोर (floor) को . (डॉट) से दिखाया जाता है।

• दीवारों (walls) को # (हैशटैग) से दिखाया जाता है।

• आरंभिक बिंदु (starting point) को बड़े अक्षर S से दर्शाया गया है।

• अंतिम कोश (end cell) को बड़े अक्षर E से दर्शाया गया है।

यदि दो कोश दीवार नहीं हैं, तो आप बाएँ, दाएँ, ऊपर या नीचे किसी भी आसन्न कोश में जा सकते हैं।

आपसे अनुरोध है कि शुरुआती कोश S से अंतिम कोश E तक के सबसे छोटे रास्ते की लंबाई ज्ञात करें।

इनपुट (Input)

इनपुट की पहली पंक्ति में दो पूर्णांक r और c दिए जाते हैं (1 ≤ r, c ≤ 1000)।

इसके बाद की अगली r पंक्तियों में ग्रिड का वर्णन करने वाले c वर्ण मौजूद होते हैं। प्रत्येक कोश या तो फ़्लोर (.) है, दीवार (#) है, आरंभिक बिंदु (S) है, या अंतिम बिंदु (E) है। यह सुनिश्चित किया जाता है कि पूरे ग्रिड में केवल एक ही S और एक ही E मौजूद हों।

आउटपुट (Output)

प्रोग्राम को S से E तक जाने वाले सबसे छोटे रास्ते की लंबाई प्रिंट करनी चाहिए।

उदाहरण (Examples)

Input

5 8
########
##.S....
....#.#.
#......#
...#...E

Output

7