Tenkici

Ο Mirko βρήκε μια συλλογή από ~N~ παιχνίδια τανκς που χρονολογούνται στον Δεύτερο Παγκόσμιο Πόλεμο στη σοφίτα του παππού του. Κάλεσε αμέσως τον φίλο του Σλάβκο να παίξει μαζί του. Έφτιαξαν ένα πεδίο μάχης - μια ξύλινη σανίδα που αποτελείται από τετράγωνα σε ~N~ σειρές και ~N~ στήλες.
Κάθε τανκ μπορεί να μετακινηθεί σε ένα από τα τέσσερα γειτονικά τετράγωνα με μία μόνο κίνηση. Ένα τανκ μπορεί να πυροβολήσει οποιοδήποτε τετράγωνο στην ίδια γραμμή ή στήλη. Ένα τανκ θεωρείται ότι προστατεύει τη σειρά και τη στήλη στην οποία βρίσκεται.
Επιπλέον, κανένα τανκ δεν μπορεί να βρίσκεται στο ίδιο τετράγωνο ανά πάσα στιγμή με ένα άλλο.
Μετά από πολλές ώρες παιχνιδιού και δύο προηγούμενες προσπάθειες, η μαμά του Mirko τους φώναξε να κατέβουν για μεσημεριανό ξανά, και αποφάσισαν να τακτοποιήσουν εκ νέου τα τανκ έτσι ώστε κάθε τανκ να προστατεύει μια διαφορετική σειρά και στήλη (που σημαίνει επίσης ότι κάθε γραμμή και στήλη περιέχει μόνο ένα τανκ).
Ωστόσο, θέλουν να το κάνουν αυτό χρησιμοποιώντας τον ελάχιστο αριθμό κινήσεων.
Γράψτε ένα πρόγραμμα που να βρίσκει τον ελάχιστο αριθμό κινήσεων που απαιτούνται για την αναδιάταξη των τανκ έτσι ώστε κάθε σειρά και κάθε στήλη να περιέχει ένα τανκ ,και αυτή τη συντομότερη ακολουθία κινήσεων.

Είσοδος

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

Έξοδος

Eκτυπώστε τον ελάχιστο αριθμό κινήσεων (καλέστε αυτόν τον αριθμό ~K~) στην πρώτη γραμμή.
Κάθε μία από τις επόμενες ~K~ γραμμές πρέπει να περιέχει τη δεξαμενή που κινείται και την κατεύθυνση προς την οποία κινείται που χωρίζονται από έναν κενό.
Οι δεξαμενές αριθμούνται από το ~1~ έως το ~N~, με τη σειρά που δίνονται στην είσοδο.
Η κατεύθυνση μπορεί να είναι ένα από τα τέσσερα κεφαλαία γράμματα: «~L~» για αριστερά, «~R~» για δεξιά, «~U~» για πάνω και «~D~» για κάτω.
Σημείωση: Η ακολουθία δεν χρειάζεται να είναι μοναδική.

Βαθμολογία

Εάν και ο αριθμός ~K~ και η ακολουθία των κινήσεων είναι σωστές, το πρόγραμμά σας θα συγκεντρώσει πλήρεις πόντους του αρχείου ελέγχου.
Εάν το πρόγραμμά σας εκτυπώνει τον σωστό αριθμό ~K~ και δεν εξάγει την ακολουθία κινήσεων ή η ακολουθία των κινήσεων είναι λανθασμένη, θα λάβετε το ~60~% των πόντων για αυτό το αρχείο ελέγχου.

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

input

5
1 1
1 2
1 3
1 4
1 5

output

10
1 D
2 D
3 D
4 D
1 D
2 D
3 D
1 D
2 D
1 D

input

5
2 3
3 2
3 3
3 4
4 3

output

8
1 R
1 R
2 U
2 U
4 D
4 D
5 L
5 L

input

6
1 1
1 2
2 1
5 6
6 5
6 6

output

8
2 R
2 D
3 D
3 R
4 U
4 L
5 L
5 U