Χώρισε τα αξιοθέατα

Υπάρχουν ~n~ αξιοθέατα στο Μπακού, αριθμημένα από ~0~ έως ~n - 1~. Υπάρχουν επίσης ~m~ δρόμοι διπλής κατεύθυνσης, αριθμημένοι από ~0~ έως ~m - 1~. Κάθε δρόμος συνδέει δύο διαφορετικά αξιοθέατα. Είναι δυνατό να ταξιδέψει κανείς από οποιαδήποτε αξιοθέατο σε οποιοδήποτε άλλο, μέσω των δρόμων.

Η Φατιμά προγραμματίζει να επισκεφθεί όλα τα αξιοθέατα μέσα σε τρεις ημέρες. Έχει ήδη αποφασίσει ότι θέλει να επισκεφθεί ~a~ αξιοθέατα την πρώτη μέρα, ~b~ αξιοθέατα τη δεύτερη μέρα, και ~c~ αξιοθέατα την τρίτη μέρα. Επομένως, πρόκειται να χωρίσει τα ~n~ αξιοθέατα σε τρία σύνολα ~A~, ~B~, και ~C~, με μεγέθη ~a~, ~b~, και ~c~, αντίστοιχα. Κάθε αξιοθέατο θα ανήκει σε ακριβώς ένα από τα σύνολα, οπότε ~a + b + c = n~.

Η Φατιμά θα ήθελε να βρει τα σύνολα ~A~, ~B~, και ~C~, έτσι ώστε τουλάχιστον δύο από τα τρία σύνολα να είναι συνδεδεμένα. Ένα σύνολο ~S~ από αξιοθέατα ονομάζεται συνδεδεμένο αν είναι δυνατό να ταξιδέψει κανείς ανάμεσα σε δύο οποιαδήποτε αξιοθέατα που ανήκουν στο ~S~ χρησιμοποιώντας τους δρομους και χωρίς να περάσει από οποιοδήποτε αξιοθέατο που δεν ανήκει στο ~S~. Μία διαμέριση από αξιοθέατα σε σύνολα ~A~, ~B~, και ~C~ καλείται έγκυρη αν ικανοποιεί τις παραπάνω συνθήκες.

Βοηθήστε τη Φατιμά να βρει μία έγκυρη διαμέριση των αξιοθεάτων (δεδομένων των ~a~, ~b~, και ~c~), ή να αποφασίσει ότι δεν υπάρχει καμία έγκυρη διαμέριση. Αν υπάρχουν περισσότερες έγκυρες διαμερίσεις, μπορείτε να βρείτε οποιαδήποτε από αυτές.

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

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

int[] find_split(int n, int a, int b, int c, int[] p, int[] q)

• ~n~: το πλήθος των αξιοθεάτων.
• ~a~, ~b~, και ~c~: τα επιθυμητά μεγέθη των συνόλων ~A~, ~B~, και ~C~.
• ~p~ και ~q~: πίνακες μήκους ~m~, που περιέχουν τα άκρα των δρόμων. Για κάθε ~i~ (~0 \le i \le m - 1~), τα ~p[i]~ και ~q[i]~ είναι τα δύο αξιοθέατα που συνδέει ο δρόμος ~i~.
• Η συνάρτηση πρέπει να επιστρέφει έναν πίνακα μήκους ~n~, ας τον ονομάσουμε ~s~. Εάν δεν υπάρχει καμία έγκυρη διαμέριση, το ~s~ πρέπει να περιέχει ~n~ μηδενικά. Διαφορετικά, για κάθε ~0 \le i \le n - 1~, το ~s[i]~ πρέπει να έχει μία από τις τιμές ~1~, ~2~ ή ~3~, που υποδεικνύουν αντίστοιχα ότι το αξιοθέατο ~i~ ανατίθεται στο σύνολο ~A~, ~B~ ή ~C~.

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

Παράδειγμα 1

Θεωρήστε την ακόλουθη κλήση:

find_split(9, 4, 2, 3, [0, 0, 0, 0, 0, 0, 1, 3, 4, 5],
                       [1, 2, 3, 4, 6, 8, 7, 7, 5, 6])

Μία δυνατή σωστή λύση είναι η ~[1, 1, 3, 1, 1, 2, 2, 3, 1, 3]~. Αυτή η λύση περιγράφει την ακόλουθη διαμέριση: ~A = {0, 1, 3, 7}~, ~B = {4, 5}~ και ~C = {2, 6, 8}~. Τα σύνολα ~A~ και ~B~ είναι συνδεδεμένα.

Παράδειγμα 2

Θεωρήστε την ακόλουθη κλήση:

find_split(6, 2, 2, 2, [0, 0, 0, 0, 0], [1, 2, 3, 4, 5])

Δεν υπάρχει καμία έγκυρη διαμέριση. Επομένως η μόνη σωστή απάντηση είναι ~[0, 0, 0, 0, 0, 0]~.

Περιορισμοί

• ~3 \le n \le 100\,000~
• ~2 \le m \le 200\,000~
• ~1 \le a, b, c \le n~
• ~a + b + c = n~
• Υπάρχει το πολύ ένας δρόμος που συνδέει κάθε ζεύγος αξιοθεάτων.
• Είναι δυνατό να ταξιδέψει κανείς ανάμεσα σε οποιαδήποτε ζεύγος αξιοθεάτων μέσω των δρόμων.
• ~0 \le p[i], q[i] \le n - 1~ και ~p[i] \ne q[i]~ για ~0 \le i \le m - 1~

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

1. (~7~ βαθμοί) Κάθε αξιοθέατο είναι άκρο το πολύ δύο δρόμων.
2. (~11~ βαθμοί) ~a = 1~
3. (~22~ βαθμοί) ~m = n - 1~
4. (~24~ βαθμοί) ~n \le 2\,500~, ~m \le 5\,000~
5. (~36~ βαθμοί) Κανένας επιπλέον περιορισμός.

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

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

• γραμμή ~1~: ~n~ ~m~
• γραμμή ~2~: ~a~ ~b~ ~c~
• γραμμή ~3 + i~ (για ~0 \le i \le m - 1~): ~p[i]~ ~q[i]~

Ο υποδειγματικός βαθμολογητής τυπώνει ακριβώς μία γραμμή, που περιέχει τον πίνακα που επιστρέφεται από την find_split.