Task Naboj

Ο κ. Šikić, ένας καθηγητής χημείας, παίζει με ~n~ μεταλλικές μπάλες και ~m~ χάλκινα σύρματα. Ένωσε μαζί μερικά ζεύγη μπάλες με ένα σύρμα έτσι ώστε όλες οι μπάλες (άμεσα ή έμμεσα) να συνδέονται μεταξύ τους. Θέλει να διδάξει τους μαθητές του για το ηλεκτρικό φορτίο και θα παρουσιάσει αυτό το φαινόμενο φορτίζοντας διαδοχικά τις μεταλλικές μπάλες.

Ο κ. Šikić μπορεί είτε να φορτίσει θετικά ή αρνητικά καθεμία από τις μπάλες. Όταν μια μπάλα φορτίζεται αρνητικά, τα ηλεκτρόνια σε όλα τα καλώδια που συνδέονται με τη σφαίρα απωθούνται προς την άλλη σφαίρα που είναι συνδεδεμένη με αυτό το καλώδιο. Αντίθετα, εάν μια μπάλα είναι θετικά φορτισμένη, τα ηλεκτρόνια από όλα τα καλώδια που συνδέονται με αυτήν τη σφαίρα έλκονται προς αυτήν. Η φόρτιση των σφαιρών έχει το ίδιο αποτέλεσμα στα καλώδια ανεξάρτητα από την προηγούμενη κατάσταση του καλωδίου.

Στην αρχή του μαθήματος όλες οι μπάλες δεν έχουν φορτίο και τα ηλεκτρόνια σε όλα τα καλώδια είναι ακίνητα. Για κάθε καλώδιο, ο κ. Šikić έχει στο μυαλό του μια συγκεκριμένη κατεύθυνση της ροής των ηλεκτρονίων. Βοηθήστε τον να βρει μια σειρά από φορτίσεις σφαιρών που έχουν ως αποτέλεσμα τις επιθυμητές ροές ηλεκτρονίων.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~n~ και ~m\;(1 \le n \le 200\,000,\;1 \le m \le 500\,000)~ από τη δήλωση της άσκησης.

Οι ακόλουθες ~m~ γραμμές περιέχουν ακέραιους αριθμούς ~a_i~ και ~b_i\;(1 \le a_i,\;b_i \le n,\;a_i \ne b_i)~ που δηλώνει ότι οι μπάλες ~a_i~ και ~b_i~ συνδέονται με ένα σύρμα και τα ηλεκτρόνια στο σύρμα πρέπει να είναι πιο κοντά στο ~a_i~, και όχι στο ~b_i~. Υπάρχει το πολύ ένα σύρμα ανάμεσα σε ένα ζευγάρι μπάλες. Όλες οι μπάλες συνδέονται άμεσα ή έμμεσα με καλώδια.

Έξοδος

Εάν είναι αδύνατο να κατευθυνθεί η ροή των ηλεκτρονίων σύμφωνα με τις επιθυμίες του κ. Šikić, τυπώστε -1. Διαφορετικά εκτυπώστε ~k~, τον απαιτούμενο δηλαδή αριθμό φορτίσεων μπάλας. Το ~k~ πρέπει να είναι μικρότερο ή ίσο με ~200\,000~.

Στις παρακάτω ~k~ γραμμές τυπώστε τους ακέραιους ~c_i~ και ~d_i\;(1 \le c_i \le n,\;0 \le d_i \le 1)~, τον αριθμό της μπάλας που ο κ. Šikić θα πρέπει να φορτίσει στο ~i~-οστό βήμα και αν θα πρέπει να φορτιστεί θετικά (συμβολίζεται με ~d_i = 1~) ή αρνητικά (~d_i = 0~). Εάν υπάρχουν πολλές λύσεις, εκτυπώστε οποιαδήποτε από αυτές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~1 \le n \le 10~
2	25	~m = n - 1~
3	70	Κανένας επιπλέον περιορισμός.

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

input

3 3
1 2
2 3
1 3

output

3
2 1
3 0
1 1

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

Αρχικά, δίνουμε στη μπάλα 2 θετικό φορτίο. Τα ηλεκτρόνια στα καλώδια μεταξύ των σφαιρών 1 και 2 και των σφαιρών 2 και 3 είναι τώρα πιο κοντά στη σφαίρα 2. Το σύρμα που συνδέει τις σφαίρες 1 και 3 παραμένει ουδέτερο.

Τώρα δίνουμε στην μπάλα 3 αρνητικό φορτίο. Η διάταξη των ηλεκτρονίων μεταξύ των καλωδίων 2 και 3 παραμένει αμετάβλητη, ενώ τα ηλεκτρόνια στο σύρμα μεταξύ 1 και 3 είναι πιο κοντά στη σφαίρα 1.

Τέλος δίνουμε στην μπάλα 1 θετικό φορτίο. Το καλώδιο μεταξύ 1 και 3 παραμένει αμετάβλητο, αλλά στο καλώδιο μεταξύ των σφαιρών 1 και 2 τα ηλεκτρόνια είναι τώρα πιο κοντά στη σφαίρα 1 και επιτυγχάνεται η επιθυμητή διάταξη.

input

4 3
1 2
3 2
2 4

output

4
2 1
4 0
3 1
1 1

input

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

output

-1