축제

rpeng: 빠른 입출력 문제를 피하려고 시간 제한을 2초로 올렸습니다. cin/cout을 사용해서 AC를 받았습니다(매우 간신히였습니다).

한 나라에 $n$개의 도시와 $m$개의 단방향 도로가 있습니다. 도시는 $1, 2, \dots, n$으로 번호가 매겨져 있습니다. 도시 $x$에서 도로를 따라 도시 $y$에 도달할 수 있으면, $y$는 $x$에서 도달 가능하다고 하며 $x \Rightarrow y$로 나타냅니다. 이 나라의 도로는 다음 성질을 만족합니다. 세 도시 $x, y, z$에 대해 $x \Rightarrow z$이고 $y \Rightarrow z$이면, $x \Rightarrow y$ 또는 $y \Rightarrow x$가 성립합니다.

축제 동안 $q$번의 퍼레이드가 열립니다. $i$번째 퍼레이드는 도시 $s_i$에서 출발해 다른 도시들을 거쳐 도시 $t_i$에서 끝납니다. 퍼레이드 중에 같은 도시를 여러 번 방문해도 됩니다. 퍼레이드를 더 흥미롭게 만들기 위해, 각 퍼레이드마다 그 퍼레이드만 사용하는 단방향 도로를 $k$개($0 \le k \le 2$) 새로 만듭니다. 다른 퍼레이드는 특정 퍼레이드를 위해 만든 도로를 지날 수 없습니다.

이제 퍼레이드 중에 방문할 수 있는 도시의 수를 구합니다. 특정 퍼레이드만을 위한 도로는 나라에 원래 있던 도로가 만족하는 성질을 따를 필요가 없다는 점에 주의하세요.

첫 줄에 도시 수 $n$, 도로 수 $m$, 퍼레이드 수 $q$, 퍼레이드마다 만들 도로 수 $k$가 주어집니다.

이어지는 $m$개의 줄에는 단방향 도로 $u \rightarrow v$가 있음을 뜻하는 정수 $u, v$가 주어집니다.

다음 $q$개의 줄에는 퍼레이드의 출발지 $s_i$와 도착지 $t_i$가 주어집니다. 같은 줄에 그 퍼레이드만을 위한 임시 단방향 도로 $a \rightarrow b$를 나타내는 정수 쌍 $a, b$가 $k$개 이어집니다.

원래 도로를 양방향으로 본다면 모든 도시는 서로 도달할 수 있습니다.

각 퍼레이드마다 답을 한 줄에 출력합니다. 답은 방문할 수 있는 도시의 수입니다. 출발지에서 도착지에 도달할 수 없으면 0을 출력합니다.

모든 테스트 케이스에 대해 $1 \le n, q \le 3 \times 10^5$, $n-1 \le m \le 6 \times 10^5$, $0 \le k \le 2$입니다.

퍼레이드 1은 출발지가 도시 1, 도착지가 도시 4입니다. 임시 도로는 $5 \rightarrow 1$입니다. 방문할 수 있는 도시는 1, 2, 4, 5입니다.

퍼레이드 2는 출발지가 도시 2, 도착지가 도시 3입니다. 임시 도로는 $5 \rightarrow 3$입니다. 방문할 수 있는 도시는 2, 3, 4, 5입니다.

퍼레이드 3은 출발지가 도시 1, 도착지가 도시 2입니다. 임시 도로는 $5 \rightarrow 2$입니다. 방문할 수 있는 도시는 1, 2, 4, 5입니다.

퍼레이드 4는 출발지가 도시 3, 도착지가 도시 4입니다. 임시 도로는 $5 \rightarrow 1$입니다. 도시 3에서 도시 4에 도달할 수 없습니다.