János gazda kicsit túlzásba vitte a kerítésépítést a földjén, ezért egy kisebb labirintus jött létre. Szerencsére a labirintus olyan, hogy bármelyik mezőjéről van kivezető út. Azt is tudjuk, hogy a külső kerítés pontosan két helyen hiányzik, tehát két kijárat van. 

Írjunk programot, ami megadja az a minimális lépésszámot, amivel garantálható, hogy kijutunk a labirintusból, bárhonnan is induljunk.

A bemenet első sora a labirintus méreteit adja meg (1<=W<=38, 1<=H<=100). A következő 2*H+1 sorban a labirintus leírása következik, a példának megfelelő formátumban.

Az egyetlen sorba azt a minimális lépésszámot kell írni, ahány lépésben (vagy kevesebbel) bármelyik mezőről kijuthatunk a labirintusból. 

Bemenet	Kimenet
5 3 +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+	9

A feladat forrása: USACO training material, Overfencing

Algoritmusok: 

megoldás