Саше и Елена живеат во село. Во задачава селото е опишано со правоаголна шема од М редови со по N знаци.
‘S’ означува поле со куќата на Саше.
‘E’ означува поле со куќата на Елена.
‘.’ означува проодно поле.
‘#’ означува баричка (непроодно поле).

Саше решил да ја побара Елена за жена. Тој сака од својата куќа до куќата на Елена да стигне што е можно побрзо, па затоа ќе го избере најкраткиот можен пат. За должина на патот се смета бројот на полиња кои ќе ги измине Саше.

Во селото во кое што живеат Саше и Елена многу често има порои, кои формираат барички. Може да се случи распоредот на баричките да е толку лош што ќе му го попречи патот на Саше.
Само во таков случај (кога нема прооден пат) Саше може да го ангажира Кире, кој работи на посипување на баричките и нивно претворање во проодни полиња. Но, Саше купил многу скап веренички прстен за Елена, па му останале пари со кои може да плати за посипување на само една баричка.

Кире пак, е потајно заљубен во Елена. Доколку Саше побара од него да посипе баричка за да има пат помеѓу двете куќи, Кире мора да ја исполни задачата (ако постои таква баричка), во спротивно ќе добие отказ. Меѓутоа кога има избор од повеќе барички, Кире, во обид да го обесхрабри Саше, ќе избере да ја посипе таа баричка која ќе го направи проодниот пат помеѓу куќите на Саше и Елена да биде најдолгиот можен.

Утврдете дали може да стигне (директно или после една посипана баричка) и колкав пат треба да помине Саше за да стигне до куќата на Елена?

Влез

Во првиот ред е дадена големината на селото: два броја М и N, одделени со едно празно место (2 <= М, N <= 1000)
Во следните М редови се дадени по N знаци кои го опишуваат селото, според објаснувањето дадено во текстот.

Излез

Еден ред, кој се состои од цел број кој го означува патот (бројот на полиња) кој треба да го помине Саше. Доколку не постои начин Саше да стигне до куќата на Елена, отпечатете -1.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
4 5
S..#E
###..
#....
.....

излез
8

влез
4 3
S..
##.
.#.
E..

излез
7

влез
3 3
S.#
###
.#E

излез
-1

Објаснување за првиот пример: Саше мора да го ангажира Кире за да стигне до куќата на Елена. Кире ќе ја посипе баричката на позиција (2,2), па растојанието кое ќе го помине Саше е 8. (ќе помине низ полињата (1,2),(2,2),(3,2),(3,3),(3,4),(3,5),(2,5),(1,5))

Објаснување за вториот пример: Саше нема да го ангажира Кире затоа што постои пат кој не е попречен од барички.

Објаснување за третиот пример: Саше не може да стигне до куќата на Елена после посипување на најмногу една баричка.