승현이는 곧 개최되는 KOI 전국본선을 대비하기 위해 그래프 이론을 공부하고 있습니다. 요즘 승현이는 깊이우선탐색(DFS)과 너비우선탐색(BFS)의 매력에 푹 빠져 있고, 이를 이용한 문제들을 풀고 있다고 합니다. 지금 승현이는 V개 정점과 E개 간선으로 구성된 무향 그래프가 주어질 때 컴포넌트의 수를 세는 문제를 풀고 있습니다. 문제에서는 편의상 정점들에는 1,2,⋯,V의 번호를, 간선들에는 1,2,⋯,E의 번호를 붙이고, 중복된 간선은 없다고 가정했습니다.

참고: 여기서 무향 그래프가 간선으로 서로 연결되지 않은 몇 개의 그룹으로 나뉘어 있을 때, 각 연결된 정점들의 부분집합을 컴포넌트라고 합니다. 예로 들어, 아래 [그림 1]에서는 {1,2,5,8}, {3}, {4,6,7}이 각각 하나의 컴포넌트를 이루고 있습니다. [그림 2]와 같이 그래프 전체가 하나의 컴포넌트로 구성되어 있을 수도 있습니다.

승현이는 당연히 문제를 보자마자 코딩을 시작하여 DFS를 사용한 올바른 코드를 작성했지만 0점을 받았습니다. 승현이의 선생님께서 코드를 보고 "재귀 함수를 사용했다"면서 채점조차 하지 않았기 때문입니다.(?) 화가 난 승현이는 주어진 그래프에서 l, l+1, l+2, ..., r-1, r번 간선들을 destroy(l, r) 함수로 파괴하기 시작합니다. (번호가 연속적인 이유는 파괴하기 편해서라고 합니다.)

[그림 3] 위 그림에서 간선 위에 쓰인 빨간색 번호는 그 간선의 번호를 의미합니다. 승현이가 destroy(3, 5)를 호출하여 3, 4, 5번 간선이 파괴되었습니다.

그러나 승현이보다 유능한 프로그래머인 여러분은 재귀 함수를 이용하지 않고 컴포넌트의 수를 구할 수 있기 때문에, 간선이 파괴된 그래프의 컴포넌트 수를 구한 뒤 recover(l, r) 함수를 호출해 파괴된 l, l+1, l+2, ..., r-1, r번 간선들을 복구하여 승현이를 약올리고자 합니다.

[그림 4] 위 그림에서 여러분은 파괴된 그래프의 컴포넌트 수(2)를 구한 뒤 recover(3, 5) 함수를 호출하여 간선을 복원했습니다.

그러자 승현이는 destroy 함수를 계속 호출했고, 이에 일일이 대응하기에 지친 여러분은 프로그램을 작성하여 이 복잡한 작업을 대신 하게 하려고 합니다. 이제 프로그램을 작성하면 되겠네요! :)

#3649 upload 11 done - how_to_reg -

간선 파괴 timer 3s memory 512MB

#3649

간선 파괴 3s 512MB