問題

うなぎ王国のきたまさ君は今， Unagi The synthesis Programming Contest（略称: UTPC）で出題された次のような問題を解いている．

うさぎ王国には n 羽の若いオスのうさぎと n 羽の若いメスのうさぎが暮らしている． 各うさぎには 1〜2n までの番号が付いており，奇数番目がオスのうさぎ，偶数番目がメスのうさぎである． m 個の組 (a_1, b_1), ..., (a_m, b_m) が与えられ，これらは a_i 番(奇数)のオスと b_i 番(偶数)のメスが交際していることを表している． (一羽のうさぎが複数のうさぎと交際していることもある．これはうさぎの世界では常識である．） うさぎ王国のお姫様は最近うなぎ王国の王子様に振られたショックから，交際しているペアを見ていると無性に腹が立ってくる． そこで，何羽かのうさぎを国外追放することにより国内から交際しているペアを消滅させることを考えた． もちろん，国外追放するうさぎはできるだけ少ないほうが良い． そのような方法をひとつ求め，追放すべきうさぎの番号の列を出力せよ．

離散数学を極めたきたまさ君は，これは「二部グラフの最小頂点被覆」を求める問題であると瞬時に理解した． きたまさ君によると，この問題は次のようにして解くことができるらしい．

1. 各うさぎをグラフの頂点だと思い，始点から各オスのうさぎに向かって容量1の辺を，各メスのうさぎから終点に向かって容量1の辺を張る．
2. 各ペア (a_i,b_i) について a_i 番の頂点から b_i 番の頂点に向かって容量1の辺を張る．
3. 始点から終点に向かう最大流を求める．
4. 流量のある辺を除去して逆向きに付け替えたグラフ(残余グラフ)を考え，そのグラフ上で始点から到達不能なオスと到達可能なメスからなる集合が求めたい最小解．

きたまさ君はこのアルゴリズムを一瞬で実装し，提出したところ，Wrong Answer の判定を食らってしまった． きたまさ君は「天才である僕がプログラムにバグを埋め込むはずがない．出題側がなにかミスをしているのだろう．」と疑ったところ，複数の最小解がありうるにも関わらず， UTPCで使われている KMCoder というジャッジシステムでは完全一致でしか正誤が判定できない仕様になっていることに気がついた． 出題者の気持ちをエスパーしたきたまさ君は，おそらく複数ありうる解のうちで辞書順最小のものを答えれば良いはずだと考えたが，天才であるきたまさ君をもってしても辞書順最小頂点被覆はどうやって求めればいいのか分からなかった． きたまさ君のプログラムの続きを手伝ってあげよう．

※本東京大学プログラミングコンテスト(UTPC)で使われているジャッジシステム AtCoder では，KMCoder と違い，完全一致以外での正誤判定も行うことが出来る．

配点

300

入力

入力は以下の形式で与えられる．

n m
a1 b1 f1
...
am bm fm

n, m, a_i, b_i は文中で記された通りであり，a_iは奇数，b_iは偶数である． f_iはきたまさ君のプログラムにより求めた最大流において，頂点 a_i から頂点 b_i への辺に流れている流量 (0 もしくは 1) を表す． きたまさ君の求めた最大流が本当に最大流であることは保証されているが，どうしても信じられない場合は各自で最大流を求めても構わない．

制約

入力中の各変数は以下の制約を満たす．

• 1 \leq n,m \leq 10⁵

出力

追放すべきうさぎの集合のうちで辞書順最小のものを求め，一行目にその大きさ C ，続く C 行にうさぎの番号を小さい順に一つずつ出力せよ． ただし，集合 X が集合 Y より辞書順で小さいとは，それぞれ番号を小さい順に x_1,x_2,...,x_C と y_1,y_2,...,y_C とした時，ある kが存在して i=1,2,...,k-1についてx_i=y_iかつx_k\lt y_kとなることと定義する．

入力例1

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

入力例1に対する出力例

3
2
3
7

入力例2

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

入力例2に対する出力例

4
1
3
5
7

入力例3

2 2
1 4 1
3 2 1

入力例3に対する出力例

2
1
2