Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$) — количество вершин и количество ребер в графе, соответственно.

Следующие $$$m$$$ строк описывают ребра графа. $$$i$$$-е ребро представлено тройкой целых чисел $$$t_i$$$, $$$x_i$$$ и $$$y_i$$$ ($$$t_i \in [0; 1]$$$, $$$1 \le x_i, y_i \le n$$$) — типом ребра ($$$t_i = 0$$$, если ребро является неориентированным, и $$$t_i = 1$$$, если ребро является ориентированным) и вершинами, которые соединяет это ребро (неориентированное ребро соединяет вершины $$$x_i$$$ и $$$y_i$$$, а ориентированное ребро идет из вершины $$$x_i$$$ в вершину $$$y_i$$$). Гарантируется, что граф не содержит петель (ребер, идущих из вершину в саму себя) и кратных ребер (то есть для каждой пары ($$$x_i, y_i$$$) не существует других пар ($$$x_i, y_i$$$) или ($$$y_i, x_i$$$)).

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ не превосходят $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$; $$$\sum m \le 2 \cdot 10^5$$$).