Seats

Πρόκειται να διοργανώσετε ένα διαγωνισμό προγραμματισμού σε μία ορθογώνια αίθουσα, η οποία έχει ~HW~ καθίσματα διατεταγμένα σε ~H~ σειρές και ~W~ στήλες. Οι σειρές είναι αριθμημένες από το ~0~ μέχρι το ~H-1~ και οι στήλες από το ~0~ μέχρι το ~W-1~. Το κάθισμα που βρίσκεται στη σειρά ~r~ και τη στήλη ~c~ συμβολίζεται ως ~(r,\;c)~ Στον διαγωνισμό λαμβάνουν μέρος ~HW~ διαγωνιζόμενοι, αριθμημένοι από το ~0~ μέχρι το ~HW-1~ . Έχετε φτιάξει ένα διάγραμμα θέσεων, στο οποίο ο διαγωνιζόμενος ~i\;(0 \le i \le HW-1)~ βρίσκεται στο κάθισμα ~(R_{i},\;C_{i})~. Το διάγραμμα τοποθετεί ακριβώς έναν διαγωνιζόμενο σε κάθε κάθισμα.

Ένα σύνολο καθισμάτων της αίθουσας ~S~ καλείται ορθογώνιο αν υπάρχουν ακεραίοι ~r_{1}~, ~r_{2}~, ~c_{1}~ και ~c_{2}~, οι οποίοι να ικανοποιούν τις πιο κάτω συνθήκες:

• ~0 \le r_{1} \le r_{2} \le H - 1~
• ~0 \le c_{1} \le c_{2} \le W - 1~
• Το ~S~ είναι ακριβώς το σύνολο όλων των καθισμάτων ~(r,\;c)~ έτσι ώστε ~r_{1} \le r \le r_{2}~ και ~c_{1} \le c \le c_{2}~.

Ένα ορθογώνιο σύνολο αποτελούμενο από ~k~ καθίσματα ~(1 \le K \le HW)~, θεωρείται όμορφο αν στα καθίσματα που το αποτελούν κάθονται οι διαγωνιζόμενοι με αριθμούς από το ~0~ μέχρι το ~k - 1~. Η ομορφιά ολόκληρου του διαγράμματος θέσεων καθορίζεται από το πλήθος των όμορφων ορθογώνιων συνόλων καθισμάτων που υπάρχουν μέσα στο διάγραμμα. Μετά τη δημιουργία του διαγράμματος θέσεων, δέχεστε μερικά αιτήματα για να αντιμεταθέσετε ζεύγη διαγωνιζόμενων. Συγκεκριμένα, υπάρχουν ~Q~ τέτοια αιτήματα, αριθμημένα από το ~0~ μέχρι το ~Q - 1~, σε χρονολογική σειρά. Το αίτημα ~j\;(0 \le j \le Q - 1)~ ζητά να αντιμεταθέσετε τους διαγωνιζόμενους με αριθμούς ~A_{j}~ και ~B_{j}~. Αποδέχεστε αμέσως κάθε αίτημα αντιμετάθεσης και προχωράτε στην ενημέρωση του διαγράμματος. Μετά από κάθε ενημέρωση, στόχος σας είναι να υπολογίσετε την ομορφιά του υφιστάμενου διαγράμματος θέσεων.

Μορφή Εισόδου

Στην πρώτη γραμμή εισόδου δίνονται 3 θετικοί ακέραιοι, οι ~H, W, Q~, το πλήθος των σειρών, των στηλών και των ερωτημάτων. Ακολουθούν ~H\cdot W~ γραμμές, η καθεμία με 2 θετικούς ακεραίους: η ~i~-οστή γραμμή περιλαμβάνει τους αριθμούς ~R_{i-1}, C_{i-1}~: την γραμμή και στήλη του αριθμού ~i-1~ (η αρίθμηση γραμμών και στηλών ξεκινάει από το 0). Στην συνέχεια, για κάθε ερώτημα δίνεται 1 γραμμή 2 μη-αρνητικών ακεραίων, των αριθμών ~a, b~ που αντιμεταθέσουμε.

Μορφή Εξόδου

Για κάθε ερώτημα, να εκτυπώνετε νέα γραμμή με μοναδικό ακέραιο: την ομορφία του διαγράμματος μετά από την αντίστοιχη αντιμετάθεση.

Παράδειγμα 1

Είσοδος:

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

Έξοδος:

3
4

Έχουμε: ~H=2~, ~W=3~, ~R=[0, 1, 1, 0, 0, 1]~, ~C=[0, 0, 1, 1, 2, 2]~ και ~Q=2~.

Αρχικά, το διάγραμμα θέσεων είναι το πιο κάτω:

~0~	~3~	~4~
~1~	~2~	~5~

Μετά το πρώτο αίτημα (~\{0, 5\}~), το διάγραμμα θέσεων είναι το πιο κάτω:

~5~	~3~	~4~
~1~	~2~	~0~

Τα σύνολα των καθισμάτων που αντιστοιχούν στους διαγωνιζόμενους {~0~}, {~0~, ~1~, ~2~} και {~0~, ~1~, ~2~, ~3~, ~4~, ~5~} είναι ορθογώνια και όμορφα. Επομένως, η ομορφιά του διαγράμματος είναι ~3~.

Το δεύτερο ερώτημα είναι της μορφής ~\{0, 5\}~ ξανά. Μετά το αίτημα ~2~, το διάγραμμα θέσεων επιστρέφει στην αρχική του διάταξη. Τα σύνολα των καθισμάτων που αντιστοιχούν στους διαγωνιζόμενους {~0~}, {~0~, ~1~}, {~0~, ~1~, ~2~, ~3~} και {~0~, ~1~, ~2~, ~3~, ~4~, ~5~} είναι ορθογώνια και όμορφα. Επομένως, η ομορφιά του διαγράμματος είναι ~4~.

Παράδειγμα 2

Είσοδος:

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

Έξοδος:

5
3
2

Περιορισμοί

• ~1 \le H~
• ~1 \le W~
• ~HW \le 1\;000\;000~
• ~0 \le R_{i} \le H - 1\;(0 \le i \le HW - 1)~
• ~0 \le C_{i} \le W - 1\;(0 \le i \le HW - 1)~
• ~(R_{i},\;C_{i}) \neq (R_{j},\;C_{j})\;(0 \le i < j \le HW - 1)~
• ~1 \le Q \le 50000~
• ~0 \le a \le HW - 1~ για κάθε κλήση της swap_seats
• ~0 \le b \le HW - 1~ για κάθε κλήση της swap_seats
• ~a \neq b~ για κάθε κλήση της swap_seats

Υποπροβλήματα

~1~. (5 βαθμοί), ~HW \le 100~, ~Q \le 5000~
~2~. (6 βαθμοί), ~HW \le 10000~, ~Q \le 5000~
~3~. (20 βαθμοί), ~H \le 1000~, ~W \le 1000~, ~Q \le 5000~
~4~. (6 βαθμοί), ~Q \le 5000~, ~|a - b| \le 10000~ για κάθε κλήση της swap_seats
~5~. (33 βαθμοί) ~H = 1~
~6~. (30 βαθμοί) Χωρίς επιπρόσθετους περιορισμούς