Informatica Online Judge

  그래프와 쿼리 [1759 / 06DF]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[2016 나는코더다 송년 대회 (ONTAK 2011)]

Background

방향성 있는 그래프 $G$가 주어진다. 모든 간선의 길이는 1일 때, 당신은 두 가지 쿼리를 처리해야 한다.

1. 간선 하나를 제거한다.
2. 정점 1에서 정점 $i$ 까지의 최단 경로를 출력한다. 경로가 없으면 -1을 출력한다.

Input

첫번째 줄에 그래프의 정점, 간선의 수와 질의의 수를 나타내는 $n, m, q$ 가 주어진다. 정점들은 순서대로 1부터 $n$까지 번호가 매겨져 있고, 간선들은 순서대로 1부터 $m$가지 번호가 매겨져 있다. ($1 <= n <= 1,000, 1 <= m <= 100,000, 1 <= q <= 200,000$)

이후 $m$개의 줄로 간선의 정보가 주어진다. $i$ 번째 줄은 간선 $i$를 나타내며, 두 정수 $u, v$ ($1 <= u, v <= n, u ≠ v$) 로 주어진다. 정점 $u$에서 정점 $v$로 가는 간선을 의미한다.

이후 $q$개의 줄에 질의가 순서대로 주어진다. 각각의 질의는 문자 $t$ 와 정수 $p$ 로 주어진다. $t = U$거나 $t = E$이다.

만약 $t = U$ 일 경우, $p$ 번 간선이 제거된다. 이미 제거된 간선이 다시 제거되는 일은 없다. ($1 <= p <= m$)

만약 $t = E$ 일 경우, 1번 정점에서 $p$번 정점으로 가는 최단 경로의 길이를 출력한다. 간선 하나당 길이가 1이라고 가정한다. 만약 경로가 없으면 -1을 출력한다. ($2 <= p <= n$) $t = E$ 인 쿼리가 적어도 1개 있음이 보장된다.

Output

$t = E$인 질의 마다 1번 정점에서 $p$번 정점으로 가는 최단 경로의 길이를 한 줄씩 출력한다. 간선 하나당 길이가 1이라고 가정한다. 만약 경로가 없으면 -1을 출력한다. 질의가 주어진 순서대로 출력하라.

IO Example

입력
7 8 8
1 2
1 3
1 5
2 4
3 1
3 5
4 5
4 6
E 7
E 5
U 7
E 6
E 5
U 2
E 5
E 4

출력
-1
1
3
1
1
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]