Το πάρκο με τα συντριβάνια (parks)

Σε ένα κοντινό πάρκο, υπάρχουν ~n~ συντριβάνια, αριθμημένα από ~0~ έως ~n - 1~. Κάθε συντριβάνι αντιστοιχεί σε ένα σημειό στο διδιάστατο επίπεδο. Συγκεκριμένα, το ~i~-οστό συντριβάνι (~0 \le i \le n - 1~) είναι ένα σημείο (~x[i]~, ~y[i]~) όπου οι συντεταγμένες ~x[i]~ και ~y[i]~ είναι άρτιοι ακέραιοι αριθμοί. Οι θέσεις όλων των συντριβανιών είναι διαφορετικές.

Ο Τιμόθεος ο αρχιτέκτων έχει αναλάβει να κατασκευάσει μερικούς δρόμους και να τοποθετήσει ένα παγκάκι σε κάθε δρόμο. Κάθε δρόμος είναι ένα οριζόντιο ή ένα κατακόρυφο ευθύγραμμο τμήμα μήκους ~2~, του οποίου τα άκρα είναι δύο διαφορετικά συντριβάνια. Οι δρόμοι πρέπει να κατασκευαστούν έτσι ώστε να μπορεί κάποιος να ταξιδέψει από οποιοδήποτε συντριβάνι προς οποιοδήποτε άλλο συντριβάνι, κατά μήκος των δρόμων. Αρχικά δεν υπάρχει κανένας δρόμος στο πάρκο.

Για κάθε δρόμο, ακριβώς ένα παγκάκι πρέπει να τοποθετηθεί στο πάρκο και να αντιστοιχιστεί (δηλαδή, να τοποθετηθεί έτσι ώστε να βλέπει) αυτόν το δρόμο. Κάθε παγκάκι πρέπει να τοποθετηθεί σε κάποιο σημείο (~a~, ~b~) έτσι ώστε οι συντεταγμένες ~a~ και ~b~ να είναι περιττοί ακέραιοι αριθμοί. Οι θέσεις όλων των παγκακιών πρέπει να είναι διαφορετικές. Ένα παγκάκι που βρίσκεται στη θέση (~a~, ~b~) μπορεί να αντιστοιχιστεί με ένα δρόμο μόνο αν και τα δύο άκρα του δρόμου είναι κάποια από τα σημεία (~a - 1~, ~b - 1~), (~a - 1~, ~b + 1~), (~a + 1~, ~b - 1~) και (~a + 1~, ~b + 1~). Για παράδειγμα, ένα παγκάκι στη θέση (~3~, ~3~) μπορεί να αντιστοιχιστεί μόνο σε κάποιον από τους δρόμους που ορίζονται από τα εξής τέσσερα ευθύγραμμα τμήματα: (~2~, ~2~) - (~2~, ~4~), (~2~, ~4~) - (~4~, ~4~), (~4~, ~4~) - (~4~, ~2~), (~4~, ~2~) - (~2~, ~2~).

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

Λεπτομέρειες υλοποίησης

Πρέπει να υλοποιήσετε την παρακάτω συνάρτηση:

int construct_roads(int[] x, int[] y)

• ~x~, ~y~: δύο πίνακες μήκους ~n~. Για κάθε ~i~ ( ~0 \le i \le n - 1~), το συντριβάνι ~i~ βρίσκεται στο σημείο (~x[i]~, ~y[i]~), όπου οι συντεταγμένες ~x[i]~ και ~y[i]~ είναι άρτιοι ακέραιοι αριθμοί.
• Αν η κατασκευή είναι εφικτή, η συνάρτηση αυτή πρέπει να κάνει ακριβώς μία κλήση στη συνάρτηση build (βλ. παρακάτω) για να δώσει τη λύση και στη συνέχεια πρέπει να επιστρέφει 1.
• Διαφορετικά, η συνάρτηση αυτή πρέπει να επιστρέφει 0 χωρίς να κάνει καμία κλήση στη συνάρτηση build.
• Η συνάρτηση αυτή θα κληθεί ακριβώς μία φορά.

Η υλοποίησή σας μπορεί να καλεί την ακόλουθη συνάρτηση για να δώσει μία εφικτή κατασκευή των δρόμων και μία τοποθέτηση των παγκακιών:

void build(int[] u, int[] v, int[] a, int[] b)

• Έστω ~m~ το συνολικό πλήθος των δρόμων που θα κατασκευαστούν.
• ~u~, ~v~: δύο πίνακες μήκους ~m~, που παριστάνουν τους δρόμους που θα κατασκευαστούν. Οι δρόμοι είναι αριθμημένοι από ~0~ έως ~m~ - ~1~. Για κάθε ~j~ ( ~0 \le j \le m - 1~), ο ~j~-οστός δρόμος συνδέει τα συντριβάνια ~u[j]~ και ~v[j]~. Κάθε δρόμος πρέπει να είναι ένα οριζόντιο ή ένα κατακόρυφο ευθύγραμμο τμήμα μήκους ~2~. Δύο διαφορετικοί δρόμοι μπορούν να έχουν το πολύ ένα κοινό σημείο (ένα συντριβάνι). Όταν κατασκευαστούν οι δρόμοι, πρέπει να είναι δυνατό να ταξιδέψει κανείς από οποιοδήποτε συντριβάνι σε οποιοδήποτε άλλο κατά μήκος των δρόμων.
• ~a~, ~b~: δύο πίνακες μήκους ~m~, που παριστάνουν τα παγκάκια. Για κάθε ~j~ ( ~0 \le j \le m - 1~), ένα παγκάκι τοποθετείται στη θέση (~a[j]~, ~b[j]~), και αντιστοιχεί στο δρόμο ~j~. Δεν μπορούν να τοποθετηθούν δύο παγκάκια στην ίδια θέση.

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

Παράδειγμα 1

Έστω η εξής κλήση:

construct_roads([4, 4, 6, 4, 2], [4, 6, 4, 2, 4])

Αυτό σημαίνει ότι υπάρχουν 5 συντριβάνια:

• το συντριβάνι ~0~ βρίσκεται στη θέση (~4~, ~4~),
• το συντριβάνι ~1~ βρίσκεται στη θέση (~4~, ~6~),
• το συντριβάνι ~2~ βρίσκεται στη θέση (~6~, ~4~),
• το συντριβάνι ~3~ βρίσκεται στη θέση (~4~, ~2~),
• το συντριβάνι ~4~ βρίσκεται στη θέση (~2~, ~4~).
• Είναι δυνατό να κατασκευαστούν οι ακόλουθοι ~4~ δρόμοι, καθένας από τους οποίους συνδέει δύο συντριβάνια, και να τοποθετηθούν τα αντίστοιχα παγκάκια:

Η λύση αυτή φαίνεται στο ακόλουθο σχήμα:

Για να δώσει αυτή τη λύση, η συνάρτηση construct_roads πρέπει να κάνει την εξής κλήση:

• build([0, 0, 3, 4], [2, 1, 0, 0], [5, 3, 5, 3], [5, 5, 3, 3])

Στη συνέχεια πρέπει να επιστρέψει 1.

Προσέξτε ότι σε αυτή την περίπτωση, υπάρχουν περισσότερες λύσεις που ικανοποιούν τους περιορισμούς και ότι όλες θα θεωρηθούν σωστές. Για παράδειγμα, είναι επίσης σωστό να κληθεί build([1, 2, 3, 4], [0, 0, 0, 0], [5, 5, 3, 3], [5, 3, 3, 5]) και στη συνέχεια να επιστραφεί 1.

Παράδειγμα 2

Έστω η εξής κλήση:

construct_roads([2, 4], [2, 6])

Το συντριβάνι ~0~ βρίσκεται στη θέση (~2~, ~2~) και το συντριβάνι ~1~ βρίσκεται στη θέση (~4~, ~6~). Εφόσον δεν υπάρχει τρόπος να κατασκευαστούν δρόμοι έτσι ώστε να ικανοποιούνται οι περιορισμοί, η συνάρτηση construct_roads πρέπει να επιστρέφει 0 χωρίς να κάνει καμία κλήση της build.

Περιορισμοί

• ~1 \le n \le 200\,000~
• ~2 \le x[i], y[i] \le 200\,000~ (για κάθε ~0 \le i \le n - 1~)
• ~x[i]~ και ~y[i]~ είναι άρτιοι ακέραιοι (για κάθε ~0 \le i \le n - 1).
• Δεν υπάρχουν δύο συντριβάνια που να βρίσκονται στην ίδια θέση.

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

1. (~5~ βαθμοί) ~x[i]~ = ~2~ (για κάθε ~0 \le i \le n - 1~)
2. (~10~ βαθμοί) ~2 \le x[i] \le 4~ (για κάθε ~0 \le i \le n - 1~)
3. (~15~ βαθμοί) ~2 \le x[i] \le 6~ (για κάθε ~0 \le i \le n - 1~)
4. (~20~ βαθμοί) Υπάρχει το πολύ ένας τρόπος να κατασκευαστούν οι δρόμοι, έτσι ώστε να είναι δυνατό να ταξιδέψει κανείς από οποιοδήποτε συντριβάνι σε οποιοδήποτε άλλο, κατά μήκος τους.
5. (~20~ βαθμοί) Δεν υπάρχουν τετράγωνα διαστάσεων \(2 × 2\) με τέσσερα συντριβάνια στις κορυφές τους.
6. (~30~ βαθμοί) Χωρίς επιπλέον περιορισμούς.

Υποδειγματικός βαθμολογητής

Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής:

• γραμμή ~1~ : ~n~
• γραμμή ~2~ + ~i~ ( ~0 \le i \le n - 1~): ~x[i]~ ~y[i]~

Η έξοδος του υποδειγματικού βαθμολογητή είναι ως εξής:

• γραμμή ~1~: η τιμή επιστροφής της construct_roads

• Αν η τιμή επιστροφής της construct_roads είναι ~1~ και η build(~u~, ~v~, ~a~, ~b~) καλείται, ο βαθμολογητής επιπρόσθετα εκτυπώνει:

• γραμμή ~2~: ~m~

• γραμμή ~3~ + ~j~ ( ~0 \le j \le m - 1~): ~u[j]~ ~v[j]~ ~a[j]~ ~b[j]~