The Bike Trip

The weather is mild and dry, perfect for a bike trip! Hektor grabbed a map of the nearby towns and the roads connecting them (bridges, viaducts, dirt tracks, and so on) and started planning a route, but in an unusual way.

Instead of writing down which places he would visit, Hektor wrote down, in order, the types of road he would ride along. Every road has a type number, and his plan is a list of stages, where each stage means "ride $x$ roads of type $y$ in a row".

Because only the road types are fixed, the actual sequence of visited places is not unique, so many different routes may match the plan. Hektor wants to know where his trip could end. The trip always starts at place $1$. Following the plan exactly, find every place where the trip could end.

The first line contains the number of test cases $Z$ ($1 \le Z \le 5$). The descriptions of the $Z$ test cases follow.

Each test case begins with a line containing two integers $n$ and $m$ ($1 \le n \le 60$, $1 \le m \le 4000$): the number of places and the number of roads on the map. Each of the next $m$ lines contains three integers $a$, $b$, and $c$ ($1 \le a, b \le n$, $1 \le c \le 100$), meaning that from place $a$ you can travel to place $b$ along a road of type $c$. No two roads share the same start place and end place at the same time.

After the map, a line contains one integer $d$ ($1 \le d \le 100$). Each of the next $d$ lines contains two integers $x$ and $y$ ($0 \le x \le 10^9$, $1 \le y \le 100$), meaning that in this stage Hektor rides $x$ roads of type $y$.

For each test case, print two lines. The first line contains a single integer: the number of places where Hektor's trip could end. The second line lists those places in increasing order.

On the first sample map, the plan leaves no choice: Hektor rides through the places $1, 2, 3, 1, 2, 3, 4$ in order, so the trip must end at place $4$.

On the same map, a plan that rides four roads of type $1$ from the start allows two routes, $1, 2, 3, 4, 1$ and $1, 2, 3, 4, 2$, so the trip can end at place $1$ or place $2$.