Hijerarhija

Ο Krešimir έχει αρχίσει να μελετά εταιρικές δομές, συμπεριλαμβανομένων των ιεραρχιών. Παρατήρησε τους υπαλλήλους και τις σχέσεις τους μέσα σε μια εταιρεία. Σε αυτή την περίπτωση, εξετάζουμε μόνο σχέσεις ανώτερου-υφιστάμενου, δηλαδή σχέσεις όπου ένας υπάλληλος είναι άμεσα ανώτερος από έναν άλλο υπάλληλο στην εταιρεία.

Μια ιεραρχία είναι μια δομή με ~N~ υπαλλήλους και ~N-1~ σχέσεις ανώτερου-υφιστάμενου, όπου υπάρχει ένα άτομο που είναι άμεσα ή έμμεσα ανώτερο από όλους τους υπαλλήλους. Στην παρατηρούμενη εταιρεία, υπάρχουν επίσης ~N~ υπάλληλοι και ~N-1~ τέτοιες σχέσεις, αλλά δεν είναι βέβαιο αν αυτή η δομή είναι μια έγκυρη ιεραρχία ή όχι.

Ο Krešimir σας έχει ζητήσει να βοηθήσετε να απαντηθεί αυτό το ερώτημα. Έχει καταγράψει όλα τα δεδομένα στο σημειωματάριό του. Επιπλέον, στο σημειωματάριό του, θα κάνει ~Q~ μόνιμες αλλαγές, αντιστρέφοντας μια σχέση ανώτερου-υφιστάμενου έτσι ώστε ο υφιστάμενος να γίνει ανώτερος από τον πρώην ανώτερό του. Μετά από κάθε τέτοια αλλαγή, είναι απαραίτητο να απαντηθεί το ίδιο ερώτημα: είναι η τρέχουσα κατάσταση μια έγκυρη ιεραρχία;

Είσοδος

Στην πρώτη γραμμή, θα υπάρχει ένας θετικός ακέραιος ~N\;(2 \le N \le 3*10^5)~.

Στις επόμενες ~N-1~ γραμμές, για κάθε ~i = 1, 2, ..., N-1~, υπάρχει ένα ζεύγος ακεραίων ~p_i~ και ~e_i\;(1 \le p_i, e_i \le N,\;p_i \neq e_i)~, που υποδεικνύει ότι ο ~p_i~​ είναι άμεσα ανώτερος από τον ~e_i~.

Στην επόμενη γραμμή, υπάρχει ένας μη αρνητικός ακέραιος ~Q\;(0 \le Q \le 10^6)~.

Στις επόμενες ~Q~ γραμμές, υπάρχουν ζεύγη ~a_i~​, ~b_i\;(1 \le a_i, b_i \le N,\;a_i \neq b_i)~. Είναι εξασφαλισμένο ότι εκείνη τη στιγμή, ο ~a_i~​ θα είναι είτε άμεσα ανώτερος από τον ~b_i~ είτε το αντίστροφο.

Στα δεδομένα ελέγχου, είναι εξασφαλισμένο ότι θα είναι δυνατόν να επιτευχθεί τουλάχιστον μία ιεραρχία με κάποια ακολουθία αναστροφών.

Έξοδος

Στις επόμενες ~Q+1~ γραμμές, για κάθε ένα από τα δεδομένα σενάρια, είναι απαραίτητο να εκτυπώσετε εάν η τρέχουσα δομή είναι ιεραρχία, δηλαδή "DA" (ΝΑΙ) αν είναι, ή "NE"(ΟΧΙ) αν δεν είναι (χωρίς τα εισαγωγικά).

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~7~	~N \le 300,\; Q = 0~
~2~	~12~	~N,\;Q \le 300~
~3~	~16~	~N,\;Q \le 1000~
~4~	~15~	~Q = 0~
~5~	~23~	Για κάθε ~i = 1, 2, ..., N-1~, θα ισχύει ότι ~i~ θα είναι άμεσα ανώτερος από τον ~i + 1~, είτε το αντίστροφο.
~6~	~17~	Κανένας επιπλέον περιορισμός.

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

1ο

input

3
1 2
1 3
3
1 2
1 2
1 3

output

DA
DA
DA
DA

2ο

input

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

output

DA
NE
DA
DA
NE