TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

80.0% (8/10)

Submission's AC Ratio

22.6% (19/84)

Tags

Description

傳說中,土撥鼠是一種神奇的動物,牠們不只會挖地道、會飛,還會電人。

但是會飛的土撥鼠太難追蹤了,而電人的土撥鼠會把你電爆,所以我們只考慮挖地道的土撥鼠。

現在有N個土撥鼠巢穴,從0編號到N-1,但是沒有任何的地道。土撥鼠可能會挖出一些雙向通行的地道,挖好的地道也有可能會崩塌。

所以你想要知道在某個時間點,如果選一些巢穴監視,裡面有沒有可能有一些土撥鼠可以透過地道,跑到你沒有選到的巢穴躲避你的監視。

Input Format

第一行有兩個整數N、M,代表有N個巢穴、M筆操作。

接下來M行,每行有一個操作。
如果是0 A B,代表土撥鼠挖出了一條新的A, B間的地道。
如果是1 A B,代表A, B間的其中一條地道崩塌,土撥鼠不能再從這條地道通過。
如果是2 K A1 A2 ... AK,代表詢問這個時間點,是否有任何地道從這些巢穴通往其它的巢穴。

保證地道崩塌之前一定存在這條地道,一筆查詢中所有的點不會重複,且一組起終點相同的地道不會超過1000條。注意可能有A, A間的地道。

以下的S代表所有詢問中K的總和,E代表過程中最多會有幾條地道。
對於5%的測資,$ N \leq 10; M, S \leq 100 $。
對於5%的測資,$ N \leq 30; M, S \leq 250 $。
對於5%的測資,$ N \leq 100; M, S \leq 2 \times 10^ 4 $。
對於10%的測資,$ N \leq 100; M \leq 3 \times 10^ 4 ; S \leq 10^ 5; E \leq 5000 $。
對於15%的測資,$ N \leq 1000; M, S \leq 6 \times 10^ 5; E \leq 2 \times 10^ 5 $。
對於20%的測資,$ N \leq 3000 $。
對於20%的測資,$ N \leq 10^ 5; M, S \leq 5 \times 10^ 6 $。
對於所有的測資,$ N \leq 5 \times 10^ 5; M, S \leq 10^ 7; E \leq 7 \times 10^ 5 $。

Output Format

對於每一筆詢問,如果不存在通往其它巢穴的地道,輸出一行1,否則輸出一行0。

Sample Input

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

Sample Output

1
1
0
1

Hints

測資很大,所以請不要使用完全不優化的cin/cout。

Problem Source

NT

Subtasks

For Testdata: 0 ~ 1, Score: 5
For Testdata: 2 ~ 3, Score: 5
For Testdata: 4 ~ 5, Score: 5
For Testdata: 6 ~ 7, Score: 10
For Testdata: 8 ~ 9, Score: 15
For Testdata: 10 ~ 12, Score: 20
For Testdata: 13 ~ 13, Score: 20
For Testdata: 14 ~ 15, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 102400 262144
1 1000 102400 262144
2 1000 102400 262144
3 1000 102400 262144
4 1000 102400 262144
5 1000 102400 262144
6 1000 102400 262144
7 1000 102400 262144
8 1000 102400 262144
9 1000 102400 262144
10 5000 102400 262144
11 7000 102400 262144
12 7000 102400 262144
13 5000 102400 262144
14 7000 102400 262144
15 7000 102400 262144