Trokuti

Ένας ακατεύθυντος γράφος με ~6*N~ κορυφές και ~M~ ακμές δίνεται. Μια πρόσθετη ιδιότητα του γράφου είναι ότι μπορεί να διαμεριστεί σε ~2*N~ μη επικαλυπτόμενα τρίγωνα.

Βρείτε ~N~ μη επικαλυπτόμενα τρίγωνα στον γράφο.

Είσοδος

Στην πρώτη γραμμή, δίνεται ένας φυσικός αριθμός ~T\;(1 \le T \le 100)~, ο οποίος δηλώνει τον αριθμό των περιπτώσεων δοκιμής.

Ακολουθούν ~T~ μπλοκ δεδομένων.

Στην πρώτη γραμμή κάθε μπλοκ, υπάρχουν φυσικοί αριθμοί ~N~ και ~M\;(1 \le N \le 300,\;0 \le M \le 10^6)~.

Στις επόμενες ~M~ γραμμές, υπάρχουν δύο φυσικοί αριθμοί ~x~ και ~y\;(1 \le x,y \le 6*N)~, που δηλώνουν ότι υπάρχει ακμή μεταξύ των κορυφών ~x~ και ~y~.

Το άθροισμα όλων των τιμών του ~N~ σε όλες τις περιπτώσεις δοκιμής δεν θα υπερβαίνει το ~300~.

Έξοδος

Για κάθε περίπτωση δοκιμής, εκτυπώστε ~N~ γραμμές, κάθε γραμμή περιέχει τρεις φυσικούς αριθμούς ~a~, ~b~, ~c\;(1 \le a,b,c \le 6*N)~, που δηλώνουν ότι οι κορυφές ~a~, ~b~ και ~c~ σχηματίζουν ένα τρίγωνο.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~13~	~M = 6*N~
~2~	~18~	~N = 3,\; T = 1~
~3~	~18~	~N = 6,\; T = 1~
~4~	~71~	Κανένας επιπλέον περιορισμός

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

1ο

input

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

output

1 2 3

2ο

input

1
3 26
4 7
4 9
7 9
4 5
4 8
5 8
4 12
4 18
12 18
3 7
3 9
15 5
15 8
6 13
6 1
13 1
6 14
6 17
14 17
6 2
6 10
2 10
16 13
16 1
11 14
11 17

output

1 6 13
3 7 9
4 5 8