題目描述

天宮四號與空間站的對接令人興奮，隨著國家的航天事業(yè)的蓬勃發(fā)展，空間站與空間站之間的聯(lián)系愈發(fā)緊密。為了以后能夠知道哪些空間站可以相連，假設(shè)現(xiàn)在有N個空間站，有M條航道相連，如果某條航道被廢棄后，A空間站無法到達B空間站，那么稱這條航道為A，B空間站之間的航橋，現(xiàn)在我們想實時知道一些空間站之間有幾條航橋。在詢問的過程中，有些航道會被廢棄掉。 你能想出最快速的算法，找出航橋嗎？

輸入說明

第一行N，M表示有N個空間站，M條航道，1 ≤ N ≤ 30000，1 ≤ M ≤ 100000，詢問數(shù)加刪除數(shù)不多于40000。

接下來M行表示M條航道，每行兩個整數(shù)，表示兩個空間站有航道相連。然后每行三個整數(shù)C、A、B：如果C=0表示A和B空間站之間的航道被永久刪除；如果C=1表示詢問A和B空間站間有幾條航橋；如果C=-1則輸入數(shù)據(jù)結(jié)束。保證空間站任意時刻都聯(lián)通。

輸出說明

對于每一個詢問，給出航橋的數(shù)量，每次詢問結(jié)果一行。

輸入樣例

5 5

1 2

1 3

3 4

4 5

4 2

1 1 5

0 4 2

1 5 1

-1

輸出樣例

1

3

大致思路：

在一棵樹上，多加一條邊，連接這個邊兩頂點的簡單路徑，就必然不可能是題目說的那種割邊。故簡單路徑上每個頂點權(quán)重為0

那么簡單路徑上所有的頂點就是只有0和1兩種權(quán)值，兩點之間割邊數(shù)量就是兩點之間頂點權(quán)為1的數(shù)量。