네트워크 뒤집기

보이지 않는 대학(Unseen University)의 학장은 통신 체계를 현대화하기로 하고, 양방향으로 연결된 호스트들로 이루어진 컴퓨터 네트워크를 설치했다. 호스트에는 $1$번부터 $h$번까지 차례로 번호가 매겨져 있다. 그런데 이 환경은 마법의 기운이 매우 강해서, 네트워크의 구조가 무작위로, 그리고 자주 바뀐다.

그래서 어떤 호스트에 도달할 수 있고 어떤 호스트에는 도달할 수 없는지를 아는 것이 매우 중요하다. 이러한 구조 변화는 네트워크에 영향을 주지 않고 관찰할 수 있으므로, 현재 네트워크의 상태는 언제든지 알 수 있다.

약속에 따라, 중심 호스트인 $1$번 호스트에서 $10$번 이하의 홉(hop)으로 도달할 수 있는 호스트를 온라인(online) 이라고 부른다. 어떤 호스트는 $1$번에서 도달할 수는 있지만 온라인은 아닐 수 있는데, 이는 그 호스트로 이어지는 모든 경로의 길이가 $10$홉보다 길기 때문이다. 학장은 이러한 호스트가 몇 개인지 알고 싶어 한다.

첫째 줄에는 테스트 케이스의 개수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 호스트의 개수를 나타내는 정수 $h$가 한 줄에 주어진다 ($1 \le h \le 3000$).
• 처음에 존재하는 연결의 개수를 나타내는 정수 $c$가 한 줄에 주어진다 ($1 \le c \le 1500$).
• 이어서 $c$개의 줄에 각각 두 정수 $p$와 $q$가 주어진다. 이는 처음에 호스트 $p$와 $q$ 사이에 연결이 존재함을 뜻한다.
• 연결 변경의 횟수를 나타내는 정수 $l$이 한 줄에 주어진다 ($1 \le l \le 1500$).
• 이어서 $l$개의 줄에 각각 두 정수 $r$과 $s$가 주어진다. 이는 호스트 $r$과 $s$ 사이의 연결을 뒤집는다는 뜻이다. 즉, 현재 연결이 있으면 사라지고, 없으면 새로 생긴다.

마법의 환경 때문에 $p$, $q$, $r$, $s$에 대해 보장되는 것은 각각이 $1 \dots h$ 범위 안에 있다는 것뿐이다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 이는 $1$번 호스트에서 도달할 수 있지만 온라인은 아닌 호스트의 개수, 즉 $1$번 호스트로부터의 최단 경로 길이가 $10$홉보다 긴 호스트의 개수이다.