Equivalent Vertices

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。 園児の一人であるゆう君は,プログラミングと同じくらいお絵描きが大好きだ。 これまでゆう君は丸と六角形と矢印で沢山絵を書いてきた。 ある日ゆう君はこれらの絵がグラフであることを知る。 丸と六角形は頂点と呼ばれ,矢印は辺と呼ばれているらしい。 ゆう君は2つの頂点間を結ぶようにして矢印を描き、更にその上に0か1を書く。 このように,辺に重み(0または1)があり有向な辺からなるグラフは重み付き有向グラフと呼ばれる。 また,頂点と数字x(0または1)が与えられた時,その頂点から出ている矢印のうち,xと同じ重みを持つ矢印に従って別の頂点に移動することをxに従って遷移すると言う。 今日ゆう君は0と1からなるどのような数列に従って遷移しても最終的に到達する頂点の種類(丸または六角形)が一緒であるような頂点の対が存在することに気がついた。 これについてゆう君は一つの問題を思いついた。

Problem

重み付き有向グラフが与えられる。 このグラフの各頂点は0から順番にn-1まで番号が割り振られている。 また,各頂点はそこから重みが0の辺と1の辺の合計2本の辺が出て行く。 さらに,頂点には丸い頂点か六角形の頂点の2種類が存在し,各頂点はそれらのいずれかである。 以下にSample Input 2で与えられる重み付き有向グラフを示す。

図1. Sample Input 2

以下の形式でm個の質問が与えられるので、それぞれについて答えを出力せよ。

• 頂点の番号qが与えられるので,この頂点と等価な頂点の数を出力せよ

2つの頂点a,bが以下の2つの条件を満たすとき,aとbは等価である。

1. aとbは同じ種類の頂点である
2. 0と1からなる長さ1以上の任意の数列について,それに従ってaとbのそれぞれから遷移を開始したとき最終的に到達する頂点の種類が同じである

例えば,図1の頂点3から数列0,0,1,0に従って遷移を開始すると, 3→2→1→1→1の順番で遷移し最終的に到達する頂点は1である。

Sample Input 2 において,頂点0と頂点2,頂点0と頂点4は等価である。 頂点0と頂点4について考える。 これらは両方とも丸い頂点であるため1つめの条件を満たす。 また,これらの頂点から0または1で遷移した結果到達する頂点は1か5である。 頂点1,5はそれぞれどのような数列に従って遷移してもその頂点に止まり続ける。 また,両方とも六角形の頂点である。 これより,頂点0と頂点4はどのような数列に従って遷移しても最終的に到達する頂点は六角形の頂点であるため2つめの条件も満たす。 条件を2つとも満たすので頂点0と頂点4は等価である。 最終的に到達する頂点は種類が同じであれば良いため,頂点の番号が同じである必要はないことに注意せよ。 また,頂点0と頂点1は等価でない。 頂点0は丸い頂点で頂点1は六角形頂点なので,1つめの条件を満たさない。

Input

n m
v0 s0 t0
v1 s1 t1
…
vn−1 sn−1 tn−1
q0
q1
…
qm−1

• v_i,s_i,t_iはそれぞれi番の頂点の種類,0による遷移先の頂点番号,1による遷移先の頂点番号
• v_iが0のとき,i番の頂点は丸い頂点であり,1のとき六角形の頂点
• q_jはj番目の質問で与えられる頂点の番号

Constraints

• 入力は全て整数として与えられる
• 1 ≤ n ≤ 3000
• 1 ≤ m ≤ n
• 0 ≤ s_i,t_i,q_j ≤ n-1
• 0 ≤ v_i ≤ 1
• 与えられるグラフの辺が双方向に移動できるものとしたとき,任意の2点を結ぶような辺の集合が存在する, つまり与えられるグラフは連結である

Output

各質問で与えられる頂点の番号q_jに対して,それと等価な頂点の数をそれぞれ一行に出力せよ。

Sample Input 1

2 1
0 0 1
0 1 0
0

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3
2
3
1
3
2