AT_arc229_e [ARC229E] Taka and Hashi

Takahashi is known for being able to split into the famous comedy duo "Taka and Hashi", that is, Taka and Hashi. When Taka and Hashi merge, they return to being the original Takahashi. There is a connected undirected graph with $ N $ vertices and $ M $ edges, and each edge is labeled with $ 1 $ , $ 2 $ , or $ 3 $ . The $ i $ -th edge connects vertices $ u_i $ and $ v_i $ , and is labeled $ l_i $ . The graph does not contain self-loops, but may contain multi-edges. Each edge can be traversed by only one of Takahashi, Taka, and Hashi, and an edge labeled $ 1 $ , $ 2 $ , or $ 3 $ can be traversed only by Takahashi, Taka, or Hashi, respectively. Initially, Takahashi is at vertex $ 1 $ . Takahashi and the others can perform the following operations in any order, zero or more times. - Takahashi splits into Taka and Hashi at the vertex where he currently is. At this point, both Taka and Hashi are at that vertex. - One of the currently existing people moves by traversing one edge that they are able to traverse. - When Taka and Hashi are at the same vertex, they merge at that vertex and return to being Takahashi. Enumerate, in ascending order, all vertices where Takahashi can be after performing a sequence of operations. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case $ \mathrm{case}_t $ is given in the following format: > $ N $ $ M $ $ u_1 $ $ v_1 $ $ l_1 $ $ u_2 $ $ v_2 $ $ l_2 $ $ \vdots $ $ u_M $ $ v_M $ $ l_M $

Output $ 2T $ lines. For each test case, letting $ a_1,a_2,\dots,a_k $ be the sequence of numbers of the vertices satisfying the condition, listed in ascending order, output them in the following format: > $ k $ $ a_1 $ $ a_2 $ $ \dots $ $ a_k $

### Sample Explanation 1 Consider the first test case. Takahashi can move from vertex $ 1 $ to vertex $ 2 $ by traversing an edge labeled $ 1 $ . After splitting into Taka and Hashi at vertex $ 2 $ , Taka moves $ 2 \to 3 \to 4 $ and Hashi moves $ 2 \to 4 $ , and by merging at vertex $ 4 $ , it is possible to make Takahashi be at vertex $ 4 $ . Furthermore, Takahashi can move to vertex $ 5 $ by traversing an edge labeled $ 1 $ . It is impossible to make Takahashi be at vertex $ 3 $ , so the vertices satisfying the condition are $ 1,2,4,5 $ . ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq N \leq 2 \times 10^5 $ - $ N-1 \leq M \leq 2 \times 10^5 $ - $ 1 \leq u_i \lt v_i \leq N $ - $ 1 \leq l_i \leq 3 $ - The given graph is connected. - The sum of $ N $ over all test cases is at most $ 2 \times 10^5 $ . - The sum of $ M $ over all test cases is at most $ 2 \times 10^5 $ . - All input values are integers.