あなたはツリーライトというツリー状の照明器具を買ってきた。
この照明器具にはn個の接点があり、それぞれ0からn−1までの番号がついている。各接点は10段階の明るさを表現できる電球と、電球の状態を切り替えるための装置で構成されている。最初、すべての接点の電球の明るさは0である。
また、接点と接点の間にはケーブル線がある。すべての接点はn−1本のケーブル線によって繋がれており、接点0を上にして吊り下げられる。ここで、接点iから下方向に0本以上のケーブル線を介して、接点iと繋がる接点の集合を、接点iを根とした部分木と呼ぶ。
あなたはこの照明器具に対し、以下のいずれかの行動をとる。
q回の行動が与えられるので、count(r, x, y)が与えられるたびにその時点での電球の数を出力せよ。
入力は以下の形式で与えられる。
n q u1 v1 u2 v2 ... un−1 vn−1 t1 r1 x1 y1 t2 r2 x2 y2 ... tq rq xq yq
1行目にツリーライトを構成する接点の数n、あなたのとる行動の数qが空白区切りで与えられる。
続くn−1行にはケーブル線の情報が空白区切りで与えられる。i番目のケーブル線の情報は、ケーブル線iが接点uiを上にして、接点uiと接点viを繋ぐことを表す。
n+1行目以降のq行にはあなたのとる行動が空白区切りで与えられる。ti = 1ならcount(ri, xi, yi)を、ti = 2ならchange(ri, xi, yi)を表す。
各count(ri, xi, yi)について、その答えを1行に出力する。
7 5 0 1 1 2 1 3 0 4 4 5 4 6 1 0 0 9 2 0 0 5 2 1 5 8 1 0 5 8 1 0 8 8
7 7 3
7 5 0 1 1 2 2 3 0 4 4 5 5 6 2 1 0 5 2 4 0 6 2 3 5 6 2 5 6 5 1 0 0 5
5