Drvca

Η πρωταγωνίστρια αυτής της εργασίας, η Chell, πρέπει να λύσει ένα νέο παζλ που έχει βρει η GLaDOS. Η Chell βρίσκεται σε ένα δωμάτιο του οποίου η διάταξη μπορεί να αναπαρασταθεί ως ένας πίνακας διαστάσεων ~N~ σειρών και ~M~​στηλών. Κάθε κελί μπορεί να είναι ένα από τα ακόλουθα:

• Εμποδισμένο κελί​— υπάρχει ένας τοίχος σε αυτό (σημειώνεται ως "#"),
• Το κελί όπου βρίσκεται η Chell αρχικά (σημειώνεται ως​"C"),
• Το κελί στο οποίο πρέπει να φτάσει η Chell για να λύσει το παζλ (σημειώνεται ως "F") ή
• Ένα κενό κελί (σημειώνεται ως ".").

Η Chell κουβαλάει ένα όπλο πύλης, ένα όπλο με το οποίο μπορείτε να δημιουργήσετε πύλες στους τοίχους.
Σε κάθε κίνηση, μπορεί να κάνει ένα από τα παρακάτω:

• Μετακινηθεί σε ένα γειτονικό κελί χρησιμοποιώντας μία κίνηση προς τα πάνω, προς τα κάτω, προς τα αριστερά ή προς τα δεξιά (δεν μπορεί να μετακινηθεί σε κελί με έναν τοίχο μέσα σε αυτό). Αυτή η κίνηση διαρκεί μια μονάδα του χρόνου.
• Δημιουργεί μια πύλη στον τοίχο γυρνώντας προς έναν τοίχο, όχι απαραίτητα γειτονικό, προς την κατεύθυνση πάνω, κάτω, αριστερά ή δεξιά και πυροβολώντας. Η πύλη θα δημιουργηθεί μόνο στην πλευρά του τοίχου από τον οποίο χτυπήθηκε. Κάθε στιγμή, μπορούν να είναι ενεργές το πολύ δύο πύλες. Εάν μια νέα πύλη δημιουργείται τη στιγμή που δύο πύλες είναι ήδη ενεργές, αυτή που δημιουργήθηκε νωρίτερα θα εξαφανιστεί. Δεν είναι δυνατή η δημιουργία νέας πύλης στη θέση άλλης υπάρχουσας πύλης. Αυτή η κίνηση διαρκεί αμελητέο χρονικό διάστημα, δηλ. μηδενικές μονάδες χρόνου.
• Εάν βρίσκεται σε ένα κελί που είναι δίπλα σε έναν τοίχο και υπάρχει μια πύλη πάνω στον τοίχο, μπορεί να μπει στην πύλη και να βγει σε ένα μη-εμποδισμένο κελί με μια άλλη πύλη. Αυτή η κίνηση είναι δυνατή εάν υπάρχουν δύο ενεργές πύλες και διαρκεί μία μονάδα χρόνου.

Η Chell θέλει να μάθει τον ελάχιστο χρόνο που χρειάζεται για να λύσει το παζλ, δηλαδή να φτάσει στο κελί που υποδηλώνεται ως «F».

Σημείωση: Το δωμάτιο θα έχει πάντα τοίχους στα πλάγια και τα γράμματα "C" και "F" θα εμφανίζονται μόνο μία φορά στον πίνακα.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τους θετικούς ακέραιους αριθμούς ~N~ και ~M~ ~(4 \le N, M \le 500)~, τους αριθμούς από την εργασία.
Κάθε μία από τις ακόλουθες γραμμές ~N~ περιέχει ~M~ χαρακτήρες που περιγράφουν τη διάταξη του δωματίου.

Έξοδος

Πρέπει να βγάλετε τον ελάχιστο χρόνο που χρειάζεται για να λύσετε το παζλ ή "nemoguce" (χωρίς εισαγωγικά, στα Κροατικά το​"αδύνατον")​—αν δεν είναι δυνατό να το λύσετε.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας το 50% των συνολικών πόντων, θα κρατήσει ~4 \le N, M \le 15~.

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

input

4 4
####
#.F#
#C.#
####

output

2

input

6 8
########
#.##..F#
#C.##..#
#..#...#
#.....##
########

output

4

Επεξήγηση του 2ου παραδείγματος:

Ο γρίφος μπορεί να λυθεί με 8 κινήσεις, που φαίνεται στις παρακάτω εικόνες.
Στην πρώτη κίνηση, στρίβουμε προς τον αριστερό τοίχο, πυροβολούμε και δημιουργούμε μια πύλη που εμφανίζεται στον τοίχο στην 3η σειρά και στην 1η στήλη (συντεταγμένες \((3,\1)\)) από τη δεξιά πλευρά.
Στη δεύτερη κίνηση, δημιουργούμε μια πύλη από την πάνω πλευρά του τοίχου στις συντεταγμένες \((6,\2)\).
Στην τρίτη κίνηση, μπαίνουμε στην πύλη στις συντεταγμένες \((3,\1)\) και βγαίνουμε στις συντεταγμένες \((5,\2)\) - ένα μη παρεμποδισμένο πεδίο με τη δεύτερη πύλη.
Στην τέταρτη κίνηση, στρίβουμε δεξιά και δημιουργούμε μια πύλη από την αριστερή πλευρά του τοίχου στις συντεταγμένες ~(5,\;7)~.
Εφόσον υπάρχουν ήδη δύο πύλες, η μία στο πεδίο ~(3,\;1)~ εξαφανίζεται.
Στην πέμπτη κίνηση, μπαίνουμε στην πύλη στις συντεταγμένες ~(6,\;2)~ και βγαίνουμε στις συντεταγμένες ~(5,\;6)~ με τη δεύτερη πύλη.
Στην έκτη κίνηση, δημιουργούμε μια νέα πύλη από την κάτω πλευρά του τοίχου στις συντεταγμένες ~(1,\;6)~, με αποτέλεσμα η πύλη στις συντεταγμένες ~(6,\;2)~ να εξαφανίζεται.
Στην έβδομη κίνηση, μπαίνουμε στην πύλη στις συντεταγμένες (5,7) και βγαίνουμε στις συντεταγμένες ~(2,\;6)~.
Τέλος, στην όγδοη κίνηση, μετακινούμε ένα μέρος προς τα δεξιά για να τελειώσει το παιχνίδι.
Η δημιουργία πύλης στις κινήσεις ~1,\;2,\;4~ και 6 διαρκεί μηδέν χρονικά διαστήματα, ενώ η υπόλοιπη κίνηση διαρκεί μία μονάδα χρόνου, άρα ο συνολικός χρόνος που χρειάζεται για να λυθεί το παζλ είναι 4 μονάδες χρόνου.

input

4​ ​5
#####
#C#.#
###F#
#####

output

nemoguce