1891 . Groundhog 廣哈
TopCoder
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 1
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
| 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 |