Usmjeravanje

Ο Peter Pan παρακολούθησε μαθήματα επαγγελματικού προσανατολισμού, για να τον βοηθήσουν να καθορίσει το μελλοντικό του επάγγελμα. Καθώς δεν θέλει να μεγαλώσει, έφυγε και αναζήτησε καταφύγιο στη Χώρα του Ποτέ. Υπάρχουν δύο ποταμοί στη Χώρα του Ποτέ, που ρέουν από τα δυτικά προς τα ανατολικά. Στην όχθη του πρώτου ποταμού, υπάρχουν ~a~ πόλεις, που φέρουν θετικούς ακέραιους αριθμούς από το 1 έως το ~a~ προς την ίδια κατεύθυνση που κυλάει το ποτάμι. Ομοίως, στην όχθη του δεύτερου ποταμού υπάρχουν ~b~ πόλεις που φέρουν θετικούς ακέραιους αριθμούς από το 1 έως το ~b~ προς την ίδια κατεύθυνση που κυλάει το ποτάμι. Ταξιδεύοντας στη ροή του ποταμού, είναι δυνατό να φτάσετε στην πόλη ~j~ από την πόλη ~i~ αν και οι δύο αυτές πόλεις βρίσκονται στον ίδιο ποταμό και αν ~i < j~.

Οι πολίτες της Χώρας του Ποτέ σχεδιάζουν να δημιουργήσουν ~m~ πτήσεις μονής κατεύθυνσης. Δίνεται ότι η ~i~-οστή διαδρομή θα πρέπει να συνδέει την πόλη ~x_i~ από τον πρώτο ποταμό και την πόλη ~y_i~ από τον δεύτερο ποταμό, αλλά δεν έχει ακόμη αποφασιστεί η κατεύθυνση. Οι πολίτες της Χώρας του Ποτέ θα ήθελαν οι πόλεις τους να είναι όσο το δυνατόν πιο συνδεδεμένες. Εκείνη τη στιγμή ο Peter Pan συνειδητοποίησε ότι θα ήθελε να κατευθύνει δρομολόγια πτήσεων ως επάγγελμα.

Ένα ζεύγος πόλεων ονομάζεται συνδεδεμένο εάν είναι δυνατό να φτάσει κανείς στη δεύτερη πόλη ξεκινώντας από την πρώτη και αντίστροφα. Κατά τη διάρκεια του ταξιδιού, επιτρέπεται η χρήση τόσο πτήσεων όσο και διαδρομών μέσω ποταμών. Ο Peter Pan θέλει να καθορίσει τις κατευθύνσεις των διαδρομών προκειμένου να ελαχιστοποιήσει το σύνολο των πόλεων στις οποίες δεν είναι συνδεδεμένο κανένα ζεύγος πόλεων. Βοηθήστε τον Peter Pan και καθορίστε πώς να κατευθύνει τις διαδρομές και ποιο θα είναι το μέγεθος του αναφερόμενου σετ πόλεων σε αυτήν την περίπτωση.

Είσοδος

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

Η ~i~-οστή των επόμενων ~m~ γραμμών περιέχει δύο θετικούς ακέραιους ~x_i~ και ~y_i\;(1 \le x_i \le a,\;1 \le y_i \le b)~, που δηλώνουν μια διαδρομή πτήσης που συνδέει την πόλη ~x_i~ του πρώτου ποταμού και την πόλη ~y_i~ του δεύτερου ποταμού. Κανένα ζεύγος πόλεων δεν αναφέρεται περισσότερες από μία φορές.

Έξοδος

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

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~1 \le a, b, m \le 15~
2	30	~1 \le a, b \le 1000~
3	60	Κανένας επιπλέον περιορισμός.

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

input

5 3
4
1 2
2 3
3 1
5 3

output

1
1 1 0 0

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

Εάν οι πτήσεις κατευθύνονται όπως φαίνεται στην έξοδο, είναι δυνατό να φτάσετε σε οποιαδήποτε πόλη ξεκινώντας από οποιαδήποτε άλλη πόλη. Επομένως, το μεγαλύτερο σύνολο που δεν περιέχει κανένα ζεύγος συνδεδεμένων πόλεων είναι 1. Για παράδειγμα, είναι δυνατό να φτάσετε στην πόλη 1 από τον πρώτο ποταμό ξεκινώντας από την πόλη 5 από τον πρώτο ποταμό: $$\displaystyle 5(I)\rightarrow3(II)\rightarrow2(I)\rightarrow3(I)\rightarrow1(II)\rightarrow2(II)\rightarrow1(I).$$

input

8 7
7
1 3
2 1
3 4
5 6

output

9
1 0 1 1

input

6 6
4
1 2
3 2
4 3
5 6
6 5
6 7
8 7

output

5
1 0 1 1 0 1 0