Mostovi

Υπάρχουν ~2N~ πόλεις σε μια συγκεκριμένη χώρα και ένας μακρύς ποταμός που τρέχει από τα δυτικά προς τα ανατολικά. Υπάρχουν ~N~ πόλεις σε κάθε πλευρά του ποταμού. Στη βόρεια πλευρά, επισημαίνονται με αριθμούς από το ~1~ έως το \(Ν\) και στα νότια με αριθμούς από ~N + 1~ έως ~2N~. Οι πόλεις σε κάθε όχθη του ποταμού επισημαίνονται με τρόπο που η πόλη πιο ανατολικά στην όχθη έχει πάντα τη μεγαλύτερη ετικέτα.

Στη βόρεια όχθη, υπάρχει μονόδρομος από κάθε πόλη (εκτός από την πόλη ~N~) προς την πλησιέστερη πόλη ανατολικά. Στη νότια όχθη, υπάρχει μονόδρομος από κάθε πόλη (εκτός από την πόλη ~N + 1~) προς την πλησιέστερη πόλη δυτικά.

Εικόνα ~1~: Εικόνα που συνοδεύει την πρώτη δοκιμαστική περίπτωση αφού έχουν ολοκληρωθεί όλοι οι αποκλεισμοί και οι κατασκευές.

Δεδομένου του γεγονότος ότι υπάρχει πολλή κίνηση, οι δρόμοι μπορεί μερικές φορές να καταστρέφονται με αποτέλεσμα να είναι μόνιμα αποκλεισμένοι για λόγους ασφαλείας. Προκειμένου να καταστεί δυνατή η συνδεσιμότητα των πόλεων που δεν είναι απαραίτητα στην ίδια πλευρά της όχθης, οι υπεύθυνοι χτίζουν γέφυρες που συνδέουν κατευθείαν δύο πόλεις που βρίσκονται στις απέναντι όχθεις του ποταμού. Η κατασκευή γέφυρας αποτελεί μια οικονομική πρόκληση, γι'αυτό κατασκευάζονται με ιδιαίτερη προσοχή για να μην μπορούν να καταστραφούν. Για τον ίδιο λόγο, οι γέφυρες είναι αμφίδρομες, σε αντίθεση με τους φτηνούς δρόμους στις όχθες του ποταμού.Επιπλέον, οι κατασκευασμένες γέφυρες δεν θα διασταυρωθούν ποτέ, ούτε στην πόλη που ξεκινάνε ή καταλήγουν – έτσι, κάθε πόλη θα συνδέεται απευθείας με μια γέφυρα με το πολύ μία πόλη στην άλλη πλευρά του ποταμού.

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

Γράψτε ένα πρόγραμμα που θα προσομοιώνει ~M~ συμβάντα που δίνονται με χρονολογική σειρά. Κάθε γεγονός είναι είτε μία πληροφορία για έναν πρόσφατα αποκλεισμένο δρόμο ή μια πληροφορία για μια νεόδμητη γέφυρα ή μια έρευνα από έναν ταξιδιώτη σχετικά με την ύπαρξη δρόμου μεταξύ δύο πόλεων. Τα γεγονότα δίνονται στην παρακάτω μορφή:

• '~A\,G_1\,G_2~' - χτίζεται μια γέφυρα μεταξύ των πόλεων ~G_1~ και ~G_2~.
• '~B\,G_1\,G_2~' - ένας μονόδρομος μεταξύ των πόλεων ~G_1~ και ~G_2~ είναι αποκλεισμένος.
• '~Q\,G_1\,G_2~' - ένας ταξιδιώτης θέλει να μάθει εάν υπάρχει διαδρομή από την πόλη ~G_1~ στην πόλη ~G_2~, δεδομένου των διαθέσιμων δρόμων και κατασκευασμένων γεφυρών.

Στην αρχή όλοι οι δρόμοι είναι διαθέσιμοι και δεν έχουν κατασκευαστεί γέφυρες.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N (1 \le N \le 10^9)~ και ~M (1 \le M \le 200\,000)~, τον αριθμό των πόλεων σε μία όχθη του ποταμού και τον αριθμό των γεγονότων.

Κάθε μία από τις ακόλουθες γραμμές ~M~ περιέχει την περιγραφή ενός μεμονωμένου γεγονότος με τη μορφή που περιγράφεται στην αποστολή. Για τις ετικέτες της πόλης στα γεγονότα, θα ισχύει ~1 \le G_1,\,G_2 \le 2N~. Οι πόλεις ~G_1~ και ~G_2~ θα είναι πάντα διαφορετικές.

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

Έξοδος

Για κάθε ερώτημα ταξιδιώτη, πρέπει να εκτυπώσετε (με τη σειρά που δόθηκαν) στην τυπική έξοδο 'DA' (Κροατική λέξη για ναι) εάν υπάρχει διαδρομή από την πόλη ~G_1~ στην πόλη ~G_2~ ή τυπώστε 'NE' (Κροατική λέξη για όχι) διαφορετικά.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~30~ βαθμών, θα ισχύει ~N,\,M \le 1\,000~. Επιπλέον, σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 30 βαθμών, θα ισχύει ~N \le 10^9,\,M \le 1\,000~.

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

input

5 6
A 4 9
Q 1 7
B 3 2
Q 1 7
A 1 8
Q 1 7

output

DA
NE
DA

input

6 10
A 3 7
A 4 10
Q 1 11
A 12 5
Q 2 11
B 10 11
Q 2 10
Q 9 6
B 1 2
Q 1 2

output

NE
DA
DA
DA
NE