Poslozi

Το "Arrange" είναι ένα παγκοσμίως δημοφιλές flash παιχνίδι. Στο "Arrange" ο κάθε παίκτης έχει μια μετάθεση των αριθμών από ~1~ έως ~N~ και μια λίστα των επιτρεπόμενων εναλλαγών. Πρέπει να εκτελέσει μια ακολουθία εναλλαγών που να μετατρέπει την αρχική μετάθεση που έλαβε, σε διατεταγμένη ακολουθία ~1,\;2,\;3,\;4,\;5\;\ldots\;N~.
Για να μπεις στη λίστα με τις υψηλές βαθμολογίες, πρέπει να εκτελέσεις τον ελάχιστο δυνατό αριθμό από εναλλαγές. Μπορεί εσείς να μη μπορείτε να το κάνετε αυτό, αλλά μπορείτε να γράψετε ένα πρόγραμμα που να το κάνει για σας!

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς: το μήκος της αρχικής ακολουθίας ~N\; (1 \le N \le 12)~, και των αριθμό επιτρεπόμενων εναλλαγών ~M\;(1 \le M \le N * \frac {N - 1} {2})~.
Η δεύτερη γραμμή περιέχει μια μετάθεση των αριθμών απο ~1~ έως ~N~.
Οι επόμενες ~M~ γραμμές περιέχουν περιγραφές των επιτρεπόμενων εναλλαγών. Εάν η γραμμή περιέχει τους αριθμούς ~A~ και ~B~ επιτρέπεται να ανταλλάξετε τον ~A~-οστό αριθμό με τον ~B~-οστό αριθμό. Στην είσοδο δεν θα περιλαμβάνονται ποτέ δύο πανομοιότυπες εναλλαγές.
Σημείωση: τα δεδομένα των αρχείων ελέγχου πρέπει να είναι τέτοια ώστε να υπάρχει πάντα λύση, όχι απαραίτητα μοναδική.

Έξοδος

Στην πρώτη γραμμή εκτυπώστε τον ελάχιστο αριθμό εναλλαγών, ~X~.
Στις επόμενες ~X~ γραμμές εκτυπώστε τις απαιτούμενες εναλλαγές, με τη σειρά.
Σε κάθε γραμμή εκτυπώστε τον δείκτη της εναλλαγής που χρησιμοποιήθηκε. Οι εναλλαγές αριθμούνται όπως εμφανίζονται στην είσοδο, ξεκινώντας από το ~1~ και αυξάνοντας.

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

input

2 1 
2 1
1 2

output

1
1

input

3 2 
2 1 3 
1 3
2 3

output

3
2
1
2

input

5 5
1 2 3 4 5
1 5
2 5
1 4
1 1
3 5

output

0