TopCoder

User's AC Ratio

94.1% (32/34)

Submission's AC Ratio

72.7% (64/88)

Description

原題目 請按這裡觀看題目。

以下是翻譯:

有一個有 n 個代理人(包括組長)的情報組織,而代理人的編號從 1 編號到 n.

很特別的是,他們的組織結構長得像一棵根固定的樹,而編號 1 號的組長一定在根的位置。

有時候,頑固的狗仔隊會試著向員工打聽訊息,而保密的最好方式就是透露假消息。

然而,如果員工們一直透露假消息,狗仔們就會因此反轉訊息得到真正的機密!

所以員工們就需要有時透露真實的消息有時透露假的消息,讓狗仔們被虛虛實實實實虛虛搞的團團轉!

當然,改變訊息的真假必須要做的讓狗仔們看不出來,而員工們的暗號就是打噴嚏(sneeze)。

隨著一個員工的動作,他自己、自己的下級、自己的下級的下級....
就會改變自己透露的訊息(真變假、假變真)
(注意:所有員工一開始都是透露真實的訊息)

而你是一個精明的狗仔,你發現了這個秘密,因此你密集地觀察到了每個員工的暗號,你能以此做為依據,

判斷某個員工說的情報是真是假嗎?

Input Format

第 1 行有兩個整數 n , m ,分別代表有幾位員工以及有幾個動作(打噴嚏或查詢)
(1 <= n,m <= 100,000)
接下來共有 n 行,有多個整數,分別代表第 i 個員工的下級

第一個整數 k 代表該員工有幾位下級
接著跟著 k 個整數,代表該員工的下級

接下來共有 m 行,代表查詢或動作

每行有兩個整數 a,b

若a=0,代表編號b的員工打了一個噴嚏

若a=1,代表你要查詢編號為b的員工說的情報是真是假

Output Format

針對a=1的情況輸出該員工目前的情形

若他說的情報是假消息 請輸出 1

若他說的情報是真情報 請輸出 0

Sample Input

5 7
1 2
2 5 4
0
0
1 3
1 4
0 2
0 4
1 5
0 1
0 3
1 3

Sample Output

0
1
1

Hints

Problem Source

原TIOJ1272 / INOI 2008

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3
3 2500 65536 262144 4
4 2500 65536 262144 5
5 2500 65536 262144 6
6 2500 65536 262144 7
7 2500 65536 262144 8
8 2500 65536 262144 9
9 2500 65536 262144 10