TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

85.7% (12/14)

Submission's AC Ratio

68.0% (17/25)

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536
1 30000 65536 65536
2 30000 65536 65536
3 30000 65536 65536
4 30000 65536 65536
5 30000 65536 65536
6 30000 65536 65536
7 30000 65536 65536
8 30000 65536 65536
9 30000 65536 65536