TopCoder

Caido
Waimai

User's AC Ratio

86.5% (32/37)

Submission's AC Ratio

19.0% (85/447)

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%的測資,N10;M,S100
對於5%的測資,N30;M,S250
對於5%的測資,N100;M,S2×104
對於10%的測資,N100;M3×104;S105;E5000
對於15%的測資,N1000;M,S6×105;E2×105
對於20%的測資,N3000
對於20%的測資,N105;M,S5×106
對於所有的測資,N5×105;M,S107;E7×105

Output Format

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

Sample Input 1

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
1
0
1

Hints

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

Problem Source

NT

Subtasks

No. Testdata Range Score
1 0~1 5
2 2~3 5
3 4~5 5
4 6~7 10
5 8~9 15
6 10~12 20
7 13 20
8 14~15 20

Testdata and Limits

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