Teoretičar

Ο μικρός Alan βαρέθηκε και ζήτησε από τον Goran να του δώσει ένα ενδιαφέρον πρόβλημα. Δεδομένου ότι είναι απασχολημένος με την προετοιμασία για τις εξετάσεις, ο Goran μπορούσε να θυμηθεί μόνο ένα τεράστιο διμερές γράφημα από τα παλιά του χρόνια ως μέλος αγώνων διαγωνιστικού προγραμματισμού. Έδωσε το γράφημα στον Alan και είπε:​Πρέπει να χρωματίσεις τις άκρες αυτού του διμερούς γραφήματος χρησιμοποιώντας όσο το δυνατόν λιγότερα χρώματα, με τέτοιο τρόπο ώστε να μην υπάρχουν δύο άκρες του ίδιου χρώματος που να μοιράζονται έναν κόμβο.

Ο Alan έτρεξε ενθουσιασμένος στο δωμάτιό του, έβγαλε την κινητή συσκευή ανάγνωσης/εγγραφής για την κασέτα του και άρχισε να εργάζεται για το πρόβλημα. Ωστόσο, σύντομα κατάλαβε ότι κάτι του έλειπε, οπότε επέστρεψε στον Goran και είπε: Δώσε μου μια άπειρη κασέτα και θα σου λύσω το πρόβλημά σου! Ο Goran του έριξε ένα έντονο βλέμμα: Άπειρη ταινία; Εάν συνεχίσεις να θεωρητικοποιείς τα πάντα, δεν θα υπάρχει ούτε ένα πράγμα με το όνομά σου.

Αφού είδε τον Alan να αρχίζει να κλαίει, ο Goran αποφάσισε να δείξει κατανόηση: Θα σου το κάνω λίγο πιο εύκολο.
Έστω ~C~ ο μικρότερος αριθμός χρωμάτων που απαιτούνται για τη ζωγραφική του γραφήματος με τον τρόπο που περιγράφηκε. Θα σου επιτρέψω να χρησιμοποιήσεις το πολύ ~X~ χρώματα, όπου το ~X~ είναι η μικρότερη δύναμη του δύο, όχι μικρότερη από ~C~.

Βοηθήστε τον Alan να λύσει το πρόβλημα.

Σημείωση: Ένα διμερές γράφημα είναι ένα γράφημα του οποίου οι κόμβοι μπορούν να χωριστούν σε δύο σύνολα (ή πλευρές) με τέτοιο τρόπο ώστε κάθε άκρη του γραφήματος να συνδέει έναν κόμβο από το πρώτο σύνολο με έναν κόμβο από το δεύτερο σύνολο.

Είσοδος

Η πρώτη γραμμή περιέχει τρεις θετικούς ακέραιους: ~L~, ~R~ και ~M\;(1 \le L, R \le 100\,000, 1 \le M \le 500000)~, που αντιπροσωπεύουν τον αριθμό των κόμβων στη μία πλευρά του διμερούς γραφήματος, τον αριθμό των κόμβων στην άλλη πλευρά του διμερούς γραφήματος και του αριθμό των ακμών, με αυτή τη σειρά.
Ακολουθούν \(Μ\) γραμμές, η καθεμία περιέχει δύο θετικούς ακέραιους αριθμούς ~a_i\;(1 \le a_i \le L)~ και ~b_i\;(1 \le b_i \le R)~, που αντιπροσωπεύουν μια ακμή μεταξύ του ~a_i~-οστού κόμβου από την πρώτη πλευρά και του ~b_i~-οστού κόμβου από τη δεύτερη πλευρά του διμερούς γραφήματος. Όλα τα ζεύγη ~(a_i, b_i)~ θα είναι μοναδικά.

Έξοδος

Στην πρώτη γραμμή τυπώστε έναν θετικό ακέραιο ~K~, τον αριθμό των χρωμάτων που χρησιμοποιούνται.
Στις επόμενες Μ γραμμές τυπώστε έναν μόνο θετικό ακέραιο ~c_i\;(1 \le c_i \le K)~, το χρώμα της i-οστής ακμής.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 20% των συνολικών πόντων, θα ισχύει ότι ~L, R \le 100~.
Σε παραδείγματα αξίας επιπλέον 20% των συνολικών πόντων, θα ισχύει ότι ~L, R \le 5\,000~.

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

input

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

output

2
1
2
1
2
1

input

2 4 4
1 1
1 2
1 3
2 4

output

4
1
2
3
4

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

Ο ελάχιστος αριθμός χρωμάτων είναι ίσος με 3. Ωστόσο, η χρήση 4 χρωμάτων είναι επίσης αποδεκτή επειδή αυτή είναι η χαμηλότερη ισχύς των 2, που δεν είναι μικρότερη από 3.