그래프와 쿼리

방향 그래프 $G$가 주어진다. 모든 간선의 길이는 $1$이다. 다음 두 종류의 쿼리를 처리해야 한다.

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

첫째 줄에 정점의 수 $n$, 간선의 수 $m$, 쿼리의 수 $q$가 주어진다. ($1 \le n \le 1000$, $1 \le m \le 100000$, $1 \le q \le 200000$) 정점은 $1$부터 $n$까지, 간선은 $1$부터 $m$까지 번호가 매겨져 있다.

이어서 $m$개의 줄에 간선 정보가 주어진다. $i$번째 줄은 간선 $i$를 나타내며, 두 정수 $u$, $v$ ($1 \le u, v \le n$, $u \ne v$)로 이루어진다. 이는 정점 $u$에서 정점 $v$로 향하는 방향 간선을 뜻한다.

이어서 $q$개의 줄에 쿼리가 순서대로 주어진다. 각 쿼리는 문자 $t$와 정수 $p$로 주어진다. ($t \in \{U, E\}$)

• $t = U$이면 $p$번 간선을 제거한다. 이미 제거된 간선을 다시 제거하는 경우는 없다. ($1 \le p \le m$)
• $t = E$이면 정점 $1$에서 정점 $p$까지의 최단 경로 길이를 출력한다. 경로가 없으면 $-1$을 출력한다. ($2 \le p \le n$)

$t = E$인 쿼리가 적어도 하나 있음이 보장된다.

$t = E$인 쿼리마다 정점 $1$에서 정점 $p$까지의 최단 경로 길이를 한 줄에 하나씩, 쿼리가 주어진 순서대로 출력한다. 경로가 없으면 $-1$을 출력한다.