Legends

Η χώρα της Καναδίας (Canadia) αποτελείται από ένα δίκτυο πόλεων και δρόμων. Κάθε δρόμος μπορεί να διασχιστεί και προς τις δύο κατευθύνσεις. Είναι δυνατό να φτάσετε από οποιαδήποτε πόλη σε οποιαδήποτε άλλη πόλη χρησιμοποιώντας τους δρόμους.

Η Σούζι μελετά τους μύθους της δημιουργίας του καναδιακού λαού. Ενδιαφέρεται ιδιαίτερα για πέντε μύθους (που αντιστοιχούν στα πέντε επιμέρους υποπροβλήματα αυτού του προβλήματος). Οι μύθοι μοιάζουν πολύ. Καθε μύθος έχει την εξής μορφή:

Στην αρχή, το οδικό δίκτυο της Καναδίας είχε μια ιδιαίτερη δομή. Όσο περνούσε ο καιρός, το δίκτυο τροποποιήθηκε για να καλύψει τις ανάγκες του αυξανόμενου πληθυσμού της Καναδίας. Κάθε τροποποίηση είχε μία από τις ακόλουθες μορφές:

• Χτίστηκε ένας δρόμος μεταξύ δύο πόλεων που δεν είχαν ακόμη δρόμο που πήγαινε απευθείας μεταξύ τους.

• Μια νέα πόλη χτίστηκε. Οι πόλεις που χτίστηκαν με αυτόν τον τρόπο δεν ήταν αρχικά συνδεδεμένες με καμία από τις υπάρχουσες πόλεις.

• Μια πόλη ~u~ μεγαλώνει πολύ και χωρίζεται σε δύο πόλεις ~v~ και ~w~. Οι πόλεις που ενώνονταν αρχικά απευθείας στο ~u~ μέσω ενός δρόμου χωρίζονται σε σύνολα ~A~ και ~B~. Ένας δρόμος κατασκευάζεται από κάθε πόλη του ~A~ στο ~v~, από κάθε πόλη του ~B~ στο ~w~ και από το ~v~ στο ~w~. Για παράδειγμα, το

  

  γίνεται

  

Οι πέντε μύθοι διαφέρουν μόνο ως προς τη δομή με την οποία πιστεύουν ότι ξεκίνησε η Καναδία. Εδώ είναι οι πρωτότυπες δομές, σύμφωνα με κάθε μύθο:

Για κάθε υποπρόβλημα, πρέπει να πάρετε τη διάταξη της Καναδίας ως είσοδο και να καθορίσετε αν ο μύθος μπορεί να είναι σωστός.

Τα υποπροβλήματα αξίζουν το καθένα ~5~ βαθμούς.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~S~ (~1 \le S \le 5~) που αντιπροσωπεύει το υποπρόβλημα που πρέπει να λύσετε. Η δεύτερη γραμμή περιέχει έναν ακέραιο ~T~ (~1 \le T~) που αντιπροσωπεύει τον αριθμό των περιπτώσεων δοκιμής (test cases). Κάθε περίπτωση δοκιμής αποτελείται από μία άδεια γραμμή, ακολουθούμενη από δύο ακέραιους ~N~ και ~M~ (~2 \le N~, ~1 \le M~) που αντιπροσωπεύουν τον αριθμό των πόλεων και των δρόμων, αντίστοιχα. Οι πόλεις είναι αριθμημένες από το ~1~ έως το ~N~. Μετά ακολουθούν ~M~ γραμμές, με την καθεμία να περιέχει δύο ακέραιους ~a~ και ~b~ (~1 \le a, b \le N~) που αντιπροσωπεύουν δύο πόλεις που συνδέονται με ένα δρόμο. Κανένας δρόμος δεν συνδέει μία πόλη με τον εαυτό της. Δύο δρόμοι δεν συνδέουν το ίδιο ζεύγος πόλεων. Είναι δυνατό να πάτε από οποιαδήποτε πόλη σε οποιαδήποτε άλλη πόλη χρησιμοποιώντας τους δρόμους.

Στο υποπρόβλημα ~3~, μπορείτε να υποθέσετε ότι το άθροισμα του ~N~ από όλες τις περιπτώσεις δοκιμής θα είναι το πολύ ~10^5~. Σε όλα τα άλλα υποπροβλήματα, το άθροισμα του ~N~ από όλες τις περιπτώσεις δοκιμής είναι το πολύ ~1\,000~.

Το ίδιο ισχύει και για το ~M~. Πιο συγκεκριμένα, στο υποπρόβλημα ~3~, το άθροισμα του ~M~ από όλες τις περιπτώσεις δοκιμής θα είναι το πολύ ~10^5~. Σε όλα τα άλλα υποπροβλήματα, το άθροισμα του ~M~ από όλες τις περιπτώσεις δοκιμής είναι το πολύ ~1\,000~.

Έξοδος

Για κάθε περίπτωση δοκιμής, εκτυπώστε μία γραμμή που θα περιέχει τη συμβολοσειρά YES ή τη συμβολοσειρά NO.

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

input

1
2

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

7 8
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 4

output

YES
NO

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

input

2
2

2 1
1 2

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

output

NO
YES

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

input

3
2

7 8
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 4

8 8
1 2
2 3
3 4
4 5
5 6
6 1
7 3
8 7

output

YES
YES

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

input

4
2

4 4
1 2
3 4
4 1

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

output

NO
YES

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

input

5
2

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

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

output

NO
YES

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