Alkemija

Στην αρχαιότητα, όταν οι αλχημιστές έψαχναν για χρυσό, ο κόσμος ήταν εξοικειωμένος με συνολικά ​Ν διακριτές ουσίες, που συμβολίζονται με το 1 έως το N. Κατά τη διάρκεια πολλών ετών σκληρής δουλειάς, αναζητώντας τη μυστική φόρμουλα, οι αλχημιστές ανακάλυψαν μια σειρά από ενδιαφέρουσες κανονικότητες - ​αλχημικές αντιδράσεις. Κατά τη διάρκεια πολλών ετών σκληρής δουλειάς, αναζητώντας τη μυστική φόρμουλα, οι αλχημιστές ανακάλυψαν μια σειρά από ενδιαφέρουσες κανονικότητες - ​αλχημικές αντιδράσεις. Σε μια αντίδραση, είναι δυνατός ο μετασχηματισμός του συνόλου ουσιών {X₁, ​X₂, ... , X_L} σε ένα άλλο σύνολο ουσιών {​Y₁, ​Y₂, ... , Y_R}. Για παράδειγμα, το σύνολο ουσιών {1, 4, 5} μπορεί να αντιδράσει μία φορά και να δημιουργήσει το νέο σύνολο ουσιών {2, 6}.

Ο Joško είναι ένας σύγχρονος αλχημιστής και έχει M διακριτές ουσίες που συμβολίζονται με ​A₁, ​A₂ , ... , ​A_M. Έχει απεριόριστη ποσότητα κάθε ουσίας από αυτό το σύνολο. Ο Joško θέλει να μάθει ποιες ουσίες μπορεί να δημιουργήσει χρησιμοποιώντας μια λίστα με αντιδράσεις αρχαίων αλχημιστών, γι' αυτό σας ζητά να τον βοηθήσετε να λύσει αυτό το πρόβλημα.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει δύο ακέραιους αριθμούς ​N και ​M (1 ≤ ​M ≤ ​N ≤ 100.000), τους αριθμούς από την περιγραφή εργασίας.
Η δεύτερη γραμμή εισαγωγής περιέχει ​M ακέραιους αριθμούς ​A_i (1 ≤ ​A_i ≤ N), ετικέτες των ουσιών που έχει ο Joško στην αρχή.
Η τρίτη γραμμή εισαγωγής περιέχει τον ακέραιο αριθμό ​K (1 ≤ ​K ≤ 100.000), τον αριθμό των γνωστών αντιδράσεων.
Οι ακόλουθες γραμμές 3*K περιέχουν μια λίστα αντιδράσεων. Κάθε αντίδραση περιγράφεται με 3 γραμμές με τον ακόλουθο τρόπο:
● Η πρώτη γραμμή περιέχει τους ακέραιους αριθμούς ​L​ και ​R​ (1 ≤ L, R ≤ N​).
● Η δεύτερη γραμμή περιέχει ​L​ διακριτούς ακέραιους ​X_i (1 ≤ ​X_i ≤ ​N​).
● Η τρίτη γραμμή περιέχει ​R​ διακριτούς ακέραιους ​Y_i (1 ≤ ​Y_i ≤ ​N​).
● Αυτό περιγράφει την αντίδραση με την οποία το σύνολο ουσιών {X₁, ​X₂, ... , X_L} μετατρέπεται σε σύνολο ουσιών {​Y₁, ​Y₂, ... , Y_R}.
Το άθροισμα όλων των τιμών L δεν θα υπερβαίνει τις 100.000. Το άθροισμα όλων των τιμών R δεν θα υπερβαίνει τις 100.000.

Έξοδος

Η πρώτη γραμμή παραγωγής πρέπει να περιέχει τον ακέραιο αριθμό X, τον αριθμό των ουσιών που μπορούν να ληφθούν. Η δεύτερη γραμμή εξόδου πρέπει να περιέχει ​Χ διακριτούς ακέραιους αριθμούς ​B_i, ταξινομημένους κατά αύξουσα σειρά, που αντιπροσωπεύουν τις ετικέτες των λαμβανόμενων ουσιών.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας 60% των συνολικών πόντων, θα ισχύει:
● N​, ​K ≤ 500.
● Το άθροισμα όλων των τιμών ​L​ και το άθροισμα όλων των τιμών ​R​ δεν θα υπερβαίνει το 500.

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

input

4 2
1 2
2
2 1
1 2
3
2 1
1 3
4

output

4
1 2 3 4

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

Υπάρχουν 2 αντιδράσεις. Η πρώτη αντίδραση μετατρέπει το σύνολο ουσιών {1, 2} σε σύνολο ουσιών {3}. Η δεύτερη αντίδραση μετατρέπει το σύνολο ουσιών {1, 3} σε σύνολο ουσιών {4}. Ο Joško έχει αρχικά ουσίες από το σύνολο {1, 2}. Χρησιμοποιώντας την πρώτη αντίδραση, ο Joško μπορεί να αποκτήσει την ουσία 3, μετά την οποία έχει ουσίες από το σύνολο {1,2, 3}. Μετά από αυτό, χρησιμοποιώντας τη δεύτερη αντίδραση, μπορεί επίσης να αποκτήσει την ουσία 4.

input

6 3
1 4 5
3
3 2
2 3 4
1 6
1 3
4
1 5 6
1 1
6
2

output

5
1 2 4 5 6

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

Ο Joško έχει αρχικά ουσίες από το σύνολο {1, 4, 5}. Χρησιμοποιώντας τη δεύτερη αντίδραση, είναι δυνατό να ληφθεί η ουσία 6, μετά την οποία είναι δυνατή η εφαρμογή της τρίτης αντίδρασης, δίνοντας την ουσία 2. Η πρώτη αντίδραση είναι αδύνατο να εφαρμοστεί επειδή ο Joško δεν έχει την ουσία 3.