자전거 여행

덥지도 않고 비도 오지 않는, 자전거 여행에 딱 좋은 날씨다! 헥토르는 주변 마을들과 그 마을들을 잇는 도로(다리, 고가도로, 흙길 등)가 그려진 지도를 펼치고 경로를 계획하기 시작했다. 그런데 그 방식이 조금 특이했다.

어떤 장소를 지날지 적는 대신, 헥토르는 지나갈 도로의 종류를 순서대로 적어 두었다. 각 도로에는 종류를 나타내는 번호가 있으며, 그의 계획은 여러 단계로 이루어진다. 각 단계는 "$y$번 종류의 도로를 연달아 $x$개 지난다"를 뜻한다.

도로의 종류만 정해져 있으므로 실제로 지나는 장소들의 순서는 하나로 정해지지 않고, 계획에 맞는 경로가 여러 가지일 수 있다. 헥토르는 여행이 어디에서 끝날 수 있는지 알고 싶다. 여행은 항상 $1$번 장소에서 시작한다. 계획을 그대로 따랐을 때, 여행이 끝날 수 있는 모든 장소를 구하여라.

첫 번째 줄에 테스트 케이스의 수 $Z$ ($1 \le Z \le 5$)가 주어진다. 이어서 $Z$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 지도의 장소 수 $n$과 도로 수 $m$ ($1 \le n \le 60$, $1 \le m \le 4000$)이 주어진다. 다음 $m$개의 줄에는 각각 세 정수 $a$, $b$, $c$ ($1 \le a, b \le n$, $1 \le c \le 100$)가 주어지며, 이는 장소 $a$에서 장소 $b$로 종류 $c$의 도로를 통해 갈 수 있음을 뜻한다. 출발 장소와 도착 장소가 동시에 같은 도로는 두 개 이상 존재하지 않는다.

지도 정보 다음 줄에는 정수 $d$ ($1 \le d \le 100$)가 주어진다. 다음 $d$개의 줄에는 각각 두 정수 $x$, $y$ ($0 \le x \le 10^9$, $1 \le y \le 100$)가 주어지며, 이는 이 단계에서 헥토르가 종류 $y$의 도로를 $x$개 지남을 뜻한다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 번째 줄에는 헥토르의 여행이 끝날 수 있는 장소의 개수를 출력한다. 두 번째 줄에는 그 장소들을 오름차순으로 출력한다.

첫 번째 예제 지도에서는 계획을 따르는 경로가 하나뿐이다. 헥토르는 장소 $1, 2, 3, 1, 2, 3, 4$를 차례로 지나므로 여행은 반드시 장소 $4$에서 끝난다.

같은 지도에서 처음부터 종류 $1$의 도로를 $4$개 지나는 계획은 $1, 2, 3, 4, 1$과 $1, 2, 3, 4, 2$의 두 경로를 허용하므로, 여행은 장소 $1$ 또는 장소 $2$에서 끝날 수 있다.