AT_arc229_e [ARC229E] Taka and Hashi

高橋君は有名お笑いコンビ『タカアンドハシ』、すなわちタカとハシに分裂できることで知られています。タカとハシが合体すると元の高橋君に戻ります。 $ N $ 頂点 $ M $ 辺の連結無向グラフがあり、各辺には $ 1,2,3 $ のいずれかのラベルが貼られています。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結び、ラベル $ l_i $ が貼られています。グラフは自己ループを含みませんが多重辺を含む可能性があります。 各辺は高橋君・タカ・ハシのうち $ 1 $ 人しか通行できず、ラベル $ 1,2,3 $ の辺を通行できるのは、それぞれ高橋君、タカ、ハシのみです。 はじめ、高橋君は頂点 $ 1 $ にいます。高橋君たちは次の操作を自由な順序で $ 0 $ 回以上行えます。 - 高橋君が自身のいる頂点上でタカとハシに分裂する。このとき、タカとハシはともにその頂点にいる。 - 現在存在する人のうち $ 1 $ 人が、その人の通行可能な辺を $ 1 $ 本通って移動する。 - タカとハシが同じ頂点にいるとき、その頂点で二人が合体して高橋君に戻る。 一連の操作を行った後に高橋君がいることのできる頂点を、全て昇順に列挙してください。 $ T $ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケース $ \mathrm{case}_t $ は以下の形式で与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ l_1 $ $ u_2 $ $ v_2 $ $ l_2 $ $ \vdots $ $ u_M $ $ v_M $ $ l_M $

$ 2T $ 行出力せよ。 各テストケースでは、条件を満たす頂点の番号を昇順に列挙した列を $ a_1,a_2,\dots,a_k $ として以下の形式で出力せよ。 > $ k $ $ a_1 $ $ a_2 $ $ \dots $ $ a_k $

### Sample Explanation 1 $ 1 $ つ目のテストケースについて考えます。 高橋君は、ラベル $ 1 $ の辺を通って頂点 $ 1 $ から頂点 $ 2 $ へ移動できます。頂点 $ 2 $ でタカとハシに分裂した後、タカが $ 2 \to 3 \to 4 $ 、ハシが $ 2 \to 4 $ と移動し、頂点 $ 4 $ で合体することで、高橋君が頂点 $ 4 $ にいる状態を作ることができます。さらに、高橋君はラベル $ 1 $ の辺を通って頂点 $ 5 $ へ移動できます。 頂点 $ 3 $ に高橋君がいる状態を作ることはできないため、条件を満たす頂点は $ 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 $ - 入力で与えられるグラフは連結 - 全てのテストケースに対する $ N $ の総和は $ 2 \times 10^5 $ 以下 - 全てのテストケースに対する $ M $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数