분산 매트릭스

전력이 부족해서 매트릭스는 에너지를 최대한 적게 쓰도록 개조되었다. 노드는 총 $n$개이며 번호는 $1$부터 $n$까지 모두 다르다. 처음에는 발전기인 1번 노드에만 에너지가 있다.

전력이 필요한 노드는 이미 전력을 받고 있는 노드에 연결되어 그 노드로부터 에너지를 받는다. 이렇게 연결된 노드들은 트리 모양의 전력망을 이룬다. 일부 노드는 고장 날 수 있고, 고장 후 시간이 지나면 복구된다. 망에 이미 연결된 노드는 간접적으로 전력을 공급하던 노드가 고장 나더라도 다른 노드에 다시 연결되지 않는다.

노드의 불안정도는 그 노드가 마지막으로 복구된 시점부터 지난 시간이다. 아직 한 번도 고장 나지 않았다면 망에 연결된 시점부터 센다. 발전기는 시각 $0$에 연결된 것으로 본다.

$m$개의 이벤트를 처리해야 한다. $i$번째 이벤트는 시작 후 정확히 $i$초에 일어나며, 다음 중 하나이다.

• ! $x_i$ $y_i$: 노드 $y_i$가 노드 $x_i$에 연결되어 $x_i$로부터 에너지를 받기 시작한다.
• - $x_i$: 노드 $x_i$가 고장 나서 에너지 전달을 멈춘다.
• + $x_i$: 전에 고장 났던 노드 $x_i$가 복구되어 다시 에너지를 전달한다.
• ? $x_i$ $y_i$: 노드 $x_i$와 $y_i$ 쌍이 얼마나 믿을 만한지 구한다.

질의에서는 두 노드가 모두 에너지를 받는지 확인한다. 노드가 에너지를 받으려면 망에 연결되어 있고, 발전기에서 그 노드까지 가는 경로의 모든 노드(자기 자신 포함)가 고장 나지 않은 상태여야 한다. 두 노드가 모두 에너지를 받으면, $x_i$ 또는 $y_i$ 중 적어도 하나의 동작이 의존하는 모든 노드의 불안정도 합을 구한다. 즉 발전기에서 두 노드까지 가는 경로에 있는 노드들이다. 두 경로에 공통으로 있는 노드는 한 번만 센다.

첫 줄에 정수 $n$과 $m$이 공백으로 구분되어 주어진다($2 \leqslant n, m \leqslant 2 \times 10^5$). 각각 전력이 필요한 노드의 수와 처리할 이벤트의 수이다.

이어지는 $m$개의 줄 중 $i$번째 줄은 시각 $i$에 일어나는 질의를 나타낸다. 질의 종류를 나타내는 기호 뒤에 종류에 따라 정수 $x_i$ 하나, 또는 $x_i$와 $y_i$ 두 개가 공백으로 구분되어 온다($1 \leqslant x_i, y_i \leqslant n$; $x_i \neq y_i$).

종류 1 질의에서 노드 $x_i$는 이미 망에 연결되어 있고, $y_i$는 연결되어 있지 않다고 보장된다. 종류 2와 종류 3 질의에서는 노드 $x_i$가 이전에 정상이었을 때만 고장 나고, 해당 고장 이후에만 복구된다고 보장된다.

종류 4 질의마다 답을 한 줄에 출력한다. $x_i$와 $y_i$ 중 적어도 하나가 에너지를 받지 못하면 -1을 출력한다. 그렇지 않으면 발전기에서 $x_i$와 $y_i$까지 가는 경로 위 모든 노드의 불안정도 합을 출력한다.

첫 번째 예시에서 세 번째 노드가 고장 나므로 두 번째 질의 ? 2 3의 답은 -1이 된다. 첫 번째 질의의 답은 $6$인데, 발전기, 두 번째 노드, 세 번째 노드가 망에 연결된 뒤 각각 $3$초, $2$초, $1$초가 지났기 때문이다. 세 번째 질의 시점에는 발전기와 두 번째 노드의 연결 후 각각 $7$초와 $6$초가 지났다. 세 번째 노드는 1초 전에 복구되었으므로 답은 $14$이다.

두 번째 예시에서는 두 번째 노드가 고장 나므로 두 번째 질의의 답이 -1이 된다. 첫 번째 질의의 답은 첫 번째 예시와 같은 방식으로 계산한다. 세 번째 질의의 답은 $7 + 1 + 5 = 13$이다.