아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

상자의 마녀

시간 제한3초메모리 제한512 MB

요약
각 간선의 용량이 1인 그래프에서 간선을 추가하거나 삭제한 뒤마다 1번 노드에서 N번 노드로 보낼 수 있는 최대 유량을 구한다.
난이도

보통10점 중 7점

유형
그래프, 동적 계획법, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

상자의 마녀 H.N.ELLY는 어느 동영상 사이트의 열렬한 팬이다. 미키 사야카는 상자의 마녀의 강함이 그때그때 그 동영상 사이트로부터의 전송 속도에 따라 변하는 것이 아닐까 생각했다. 그래서 동영상 사이트에서 상자의 마녀가 가진 컴퓨터까지의 과거 전송 속도(단위 시간당 데이터 전송량)를 조사하려 한다.

초기 인터넷 네트워크의 구조와 그 이후 네트워크 구조의 변화를 나타내는 쿼리가 주어진다. 각 변화에 대해 변화 직후의 동영상 사이트에서 상자의 마녀가 가진 컴퓨터까지의 전송 속도를 구하라.

인터넷은 여러 전송 장치로 이루어진 것으로 보고, 각 장치를 잇는 회선은 양방향으로 정보를 보낼 수 있으며 그 전송 속도의 최대는 1이라고 한다. 또한 네트워크는 항상 동영상 사이트에서 상자의 마녀에게 보내는 데이터의 전송 속도를 최대화하도록 데이터를 나른다.

입력

입력은 다음 형식으로 주어진다.

N E Q
F1 T1
F2 T2
…
FE TE
M1 A1 B1
M2 A2 B2
…
MQ AQ BQ

N은 동영상 사이트와 상자의 마녀가 가진 컴퓨터를 포함한 전송 장치의 수이다. 번호가 1인 전송 장치는 동영상 사이트이고, 번호가 N인 전송 장치는 상자의 마녀가 가진 컴퓨터이다. E는 초기 상태에서 연결된 전송 장치 쌍의 수이고, Q는 인터넷이 변화한 횟수이다. 초기 인터넷은 Fi와 Ti가 전송 속도 1로 양방향 연결되어 있음을 나타낸다.

네트워크의 변화는 시계열 순으로 주어지고, j번째 변화는 Mj가 1이면 Aj, Bj 사이가 연결되었음을 나타내며, Mj가 2이면 Aj, Bj 사이의 연결이 끊어졌음을 나타낸다.

출력

각 변화 직후의 동영상 사이트에서 상자의 마녀가 가진 컴퓨터까지의 전송 속도를 출력하라.

제한

  • 2≤N≤500
  • 0≤E≤20,000
  • 1≤Q≤1,000
  • 1≤Fi≤N, 1≤Ti≤N, Fi≠Ti (1≤i≤E)
  • 모든 {Fi,Ti} 쌍은 서로 다르다.
  • 1≤Mj≤2, 1≤Aj≤N, 1≤Bj≤N, Aj≠Bj (1≤j≤Q)
  • 네트워크의 어느 단계에서도 다음이 성립한다: 어떤 2개의 전송 장치 사이도 많아야 1개의 회선으로만 연결되어 있다.
  • 2개의 전송 장치 사이가 이미 연결된 상태에서 그 사이를 연결하는 쿼리가 오거나, 2개의 전송 장치 사이가 회선으로 연결되지 않은 상태에서 그 사이의 연결을 끊는 쿼리가 오는 일은 없다.

예제4

  1. 예제 1

    입력
    2 1 2
1 2
2 1 2
1 2 1
    예상 출력
    0
1

  2. 예제 2

    입력
    3 0 4
1 2 3
1 2 1
1 3 1
2 2 3
    예상 출력
    0
1
2
1

  3. 예제 3

    입력
    6 4 8
1 2
1 3
4 6
5 6
1 2 4
1 3 5
1 2 5
1 3 4
2 2 4
2 3 5
1 2 4
2 2 1
    예상 출력
    1
2
2
2
2
2
2
1

  4. 예제 4

    입력
    12 38 6
1 2
1 3
1 4
1 5
2 3
2 4
2 5
2 6
2 7
2 8
2 12
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
6 9
6 10
6 12
7 8
7 9
7 10
8 9
8 10
9 10
9 11
9 12
10 11
11 12
2 6 12
2 9 12
1 9 12
1 6 12
2 6 12
1 6 12
    예상 출력
    3
2
3
4
3
4