페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4028

제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

간선 게임 7초 1024MB

문제

당신은 간선 게임에 참여했다! 간선 게임을 클리어하기 위해서는 주어지는 명령을 완벽하게 수행해야 한다.

V개의 정점과 E개의 무방향 간선이 주어진다. 정점은 1번부터 V번까지의 번호가, 간선은 1번부터 E번까지의 번호가 붙어 있다. 이 게임은 E개의 간선 중 몇 개를 골라, 해당 간선만을 거쳐 이동할 수 없는 정점 쌍의 개수를 구하는 게임이다. 즉, i와 j 사이를 선택한 간선들만을 거쳐 이동할 수 없는 (i,\ j) 쌍의 개수를 구해야 한다. (1≤i<j≤V)

간선 게임에서는 다음과 같은 명령이 주어진다. 초기 그래프 G에는 간선이 존재하지 않는다.

  • + l r : 그래프 G에 l번부터 r번까지의 간선을 추가한다. 이미 G에 존재하는 간선은 다시 추가하지 않는다.

  • - l r : 그래프 G에서 l번부터 r번까지의 간선을 제거한다. G에 존재하지 않는 간선의 경우 제거하지 않는다.

  • ? l r : 그래프 G에서 l번부터 r번까지의 간선만을 고려하였을 때, 경로가 존재하지 않는 정점 쌍의 개수를 구한다.


입력

첫 번째 줄에 정수 V,E가 공백으로 구분되어 주어진다. (2≤V≤500;\ 1≤E≤3⋅10^5)

두 번째 줄부터 E개의 줄에 걸쳐 간선의 정보가 주어진다. i번째 줄에는 i번 간선이 연결하는 두 정점 u_i와 v_i가 공백으로 구분하여 주어진다. (1≤u_i,\ v_i≤V;\ u_i≠v_i)

E+2 번째 줄에 명령의 개수 Q가 주어진다. (1≤Q≤20\ 000)

E+3 번째 줄부터 Q개의 줄에 걸쳐 명령 c_i,\ l_i,\ r_i가 공백으로 구분하여 주어진다. (c_i∈ \{ +, -, ? \};\ 1≤l_i≤r_i≤E)

c_i= ?인 명령은 하나 이상 주어진다.


출력

?인 명령이 주어질 때마다 정답을 한 줄에 하나씩 출력한다.


예제 

4 10
1 2
3 1
2 4
3 4
4 1
2 3
1 2
1 2
3 4
3 2
10
? 1 10
+ 1 2
? 1 7
+ 7 9
? 8 9
- 4 8
+ 2 6
- 3 4
? 4 5
? 1 10
6
3
4
5
0
로그인해야 코드를 작성할 수 있어요.