Okret

Ο Mirko έχει μάθει να οδηγεί, αλλά ακόμα δεν μπορεί να κάνει αναστροφή σε ένα στενό δρόμο. Γι' αυτό αποφάσισε να κάνει προπόνηση σε μια πόλη όπου οι αναστροφές απαγορεύονται παντού. Αυτή η απαγόρευση μπορεί να επισημανθεί με την ακόλουθη πινακίδα:

Ο Mirko σύντομα κατάλαβε ότι η ιδανική του πόλη δεν πρέπει να περιέχει αδιέξοδους δρόμους, αφού είναι αδύνατο να βγεις από έναν τέτοιο δρόμο χωρίς στροφή (ας υποθέσουμε ότι ο Mirko δεν μπορεί να οδηγήσει ούτε στην όπισθεν). Γράψτε ένα πρόγραμμα για να αναλύσετε έναν χάρτη της πόλης και να προσδιορίσετε εάν η πόλη είναι κατάλληλη για το Mirko (δηλαδή εάν η πόλη έχει αδιέξοδους δρόμους).
Ο χάρτης της πόλης είναι ένας πίνακας με κελιά $R\times C$, όπου κάθε κελί είναι ένα τμήμα κτιρίου (που συμβολίζεται με ${\rm X}$) ή μια επιφάνεια του δρόμου (που συμβολίζεται με μια τελεία). Από ένα κελί στην επιφάνεια του δρόμου, ο Mirko μπορεί να μετακινηθεί σε οποιοδήποτε από τα γύρω τέσσερα κελιά (πάνω, κάτω, αριστερά ή δεξιά), υπό την προϋπόθεση ότι είναι επίσης οδόστρωμα (δηλαδή όχι κτίριο).
Επίσημα, θα προσδιορίσουμε ότι μια πόλη είναι απαλλαγμένη από αδιέξοδους δρόμους εάν, ξεκινώντας από οποιοδήποτε κελί του δρόμου και πηγαίνοντας προς οποιαδήποτε από τις πιθανές κατευθύνσεις, μπορούμε να επιστρέψουμε στο κελί εκκίνησης χωρίς να κάνουμε στροφή 180 μοιρών (αλλάζοντας την κατεύθυνση μας στην αντίθετη).

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους θετικούς ακέραιους $R$ και $C(3\le R,C\le 10)$, τις διαστάσεις της πόλης.
Κάθε μία από τις επόμενες $R$ γραμμές περιέχει $C$ χαρακτήρες, με κάθε χαρακτήρα είτε "X" ή ".". Αυτοί οι $R\times C$ χαρακτήρες αντιπροσωπεύουν τον χάρτη της πόλης όπως περιγράφεται στο παραπάνω κείμενο. Τουλάχιστον δύο κελιά θα είναι επιφάνειες δρόμων και όλες οι επιφάνειες του δρόμου θα συνδέονται (δηλαδή αμοιβαία προσβάσιμες).

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει 0 εάν η πόλη δεν έχει αδιέξοδους δρόμους, διαφορετικά πρέπει να περιέχει 1.

Παραδείγματα

input

4 3
XXX
X.X
X.X
XXX

output

1

input

5 5
XX.XX
X...X
.....
X...X
XX.XX

output

1

input

3 9
...XXX...
.X.....X.
...XXX...

output

0