Sopsug

Το Grushög είναι μια αδόμητη κατοικημένη περιοχή στα περίχωρα του Lund. Αυτή τη στιγμή κατασκευάζονται όλες οι απαραίτητες υποδομές, συμπεριλαμβανομένης της πιο σημαντικής από όλες: αυτή της αποκομιδής σκουπιδιών. Όπως σε πολλές περιοχές της Σουηδίας, ένας σκουπιδοφάγος (αυτόματη αντλία αναρρόφησης σκουπιδιών) θα χρησιμοποιηθεί για τη συλλογή των σκουπιδιών. Η ιδέα είναι να μεταφέρονται τα σκουπίδια υπόγεια μέσω σωλήνων με τη χρήση πίεσης αέρα.

Υπάρχουν ~N~ κτίρια στο Grushög, αριθμημένα από ~0~ έως ~N - 1~. Αποστολή σας είναι να συνδέσετε μερικά ζεύγη κτιρίων με σωλήνες. Αν κατασκευάσετε ένα σωλήνα από το κτίριο ~u~ σε κάποιο άλλο κτίριο ~v~, το ~u~ θα στείλει όλα τα σκουπίδια του στο ~v~ (αλλά όχι προς την άλλη κατεύθυνση).

Ο στόχος σας είναι να δημιουργήσετε ένα δίκτυο από ~N - 1~ σωλήνες έτσι ώστε όλα τα σκουπίδια να καταλήγουν σε ένα κτίριο. Με άλλα λόγια, θέλετε το δίκτυο να σχηματίζει ένα δέντρο με ρίζα, όπου οι ακμές έχουν κατεύθυνση προς τη ρίζα. Ωστόσο, έχουν ήδη κατασκευαστεί ~M~ σωλήνες μεταξύ των κτιρίων. Αυτοί πρέπει να χρησιμοποιηθούν στο δίκτυό σας.

Αυτοί οι σωλήνες είναι κατευθυνόμενοι, οπότε μπορούν να χρησιμοποιηθούν μόνο προς μία κατεύθυνση.

Επιπλέον, υπάρχουν ~K~ ζεύγη κτιρίων μεταξύ των οποίων είναι αδύνατο να κατασκευαστεί ένας σωλήνας. Αυτά τα ζεύγη είναι ταξινομημένα, οπότε αν δεν είναι εφικτό να κατασκευαστεί ένας σωλήνας από ~u~ σε ~v~, ενδέχεται ωστόσο να είναι εφικτό να κατασκευαστεί ένας σωλήνας από ~v~ σε ~u~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους τρεις ακέραιους αριθμούς ~N~, ~M~ και ~K~.

Οι επόμενες γραμμές ~M~ περιέχουν δύο διακριτούς ακεραίους ~a_i, b_i~, που σημαίνει ότι υπάρχει ήδη ένας σωλήνας από ~a_i~ σε ~b_i~.

Οι υπόλοιπες ~K~ γραμμές περιέχουν δύο διακριτούς ακέραιους ~c_i, d_i~, που σημαίνει ότι είναι αδύνατο να κατασκευαστεί σωλήνας από ~c_i~ έως ~d_i~.

Όλα τα ~M + K~ διατεταγμένα ζεύγη στην είσοδο θα είναι διακριτά. Σημειώστε ότι τα ~(u, v)~ και ~(v,u)~ θεωρούνται διαφορετικά ζεύγη.

Έξοδος

Εάν δεν υπάρχει λύση, εκτυπώστε "NO".

Διαφορετικά, εκτυπώστε ~N - 1~ γραμμές, καθεμία από τις οποίες περιέχει δύο ακέραιους ~u_i, v_i~, που σημαίνει ότι πρέπει να υπάρχει ένας σωλήνας που να κατευθύνεται από ~u_i~ σε ~v_i~. Μπορείτε να εκτυπώσετε τους σωλήνες με οποιαδήποτε σειρά. Εάν υπάρχουν πολλαπλές λύσεις, μπορείτε να εκτυπώσετε οποιαδήποτε από αυτές. Να θυμάστε ότι στη λύση σας πρέπει να συμπεριληφθούν όλοι οι ήδη υπάρχοντες σωλήνες ~M~.

Περιορισμοί και βαθμολογία

• ~2 \le N \le 300\,000~
• ~0 \le M \le 300\,000~
• ~0 \le K \le 300\,000~
• ~0 \le a_i, b_i \le N - 1~ για ~i = 0, 1, \cdots, N M - 1~
• ~0 \le c_i, d_i \le N - 1~ για ~i = 0, 1, \cdots, N K - 1~

Η λύση σας θα ελεγχθεί σε ένα σύνολο ομάδων δοκιμών, καθεμία από τις οποίες αξίζει έναν αριθμό βαθμών. Κάθε ομάδα δοκιμών περιέχει ένα σύνολο δοκιμαστικών περιπτώσεων (test cases). Προκειμένου να συγκεντρώσετε τους πόντους για μια ομάδα δοκιμών, πρέπει να λύσετε όλες τις δοκιμαστικές περιπτώσεις (test cases) αυτής της της ομάδας.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~12~	~M = 0~ και ~K = 1~
~2~	~10~	~M = 0~ και ~K = 2~
~3~	~19~	~K = 0~
~4~	~13~	~N \le 100~
~5~	~17~	Είναι εγγυημένο ότι υπάρχει μια λύση με ρίζα ~0~.
~6~	~11~	~M = 0~
~7~	~18~	Κανένας επιπλέον περιορισμός.

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

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

input

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

output

4 1
3 0
1 3
2 3

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

Το σχήμα αριστερά δείχνει το πρώτο παράδειγμα με τη λύση από την έξοδο αυτού, και δείχνει σωλήνες με μαύρες ακμές (εκτός από τον ήδη κατασκευασμένο σωλήνα από ~4~ σε ~1~ που είναι μπλε). Σε αυτό το δίκτυο, όλα τα σκουπίδια θα συλλέγονται στο κτίριο ~0~. Αυτή δεν είναι η μοναδική λύση, για παράδειγμα, ο σωλήνας από ~1~ έως ~3~ μπορεί να αντικατασταθεί από έναν σωλήνα από ~0~ σε ~1~ και παραμένει μια έγκυρη λύση.

input

5 4 0
1 0
2 3
3 4
4 2

output

NO

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

Για το παράδειγμα αυτό, μπορούμε να δούμε στο δεξιό σχήμα ότι είναι αδύνατο να κατασκευαστεί μια λύση λόγω του κύκλου ~(2, 3, 4)~.

input

3 0 1
0 1

output

1 0
2 0

input

4 0 2
0 1
1 0

output

2 0
3 0
1 3