406359: GYM102388 E Stables

On Planet E, people travel by horses!

There are $$$n$$$ cities on Planet E, labeled $$$0, 1, \dots, n - 1$$$, and $$$m$$$ roads connecting the cities. For each $$$j = 0, 1, \dots, m - 1$$$, road $$$j$$$ connects city $$$x_j$$$ and city $$$y_j$$$, meaning that we can travel from city $$$x_j$$$ to city $$$y_j$$$ (and from city $$$y_j$$$ to city $$$x_j$$$) in one step. Note that $$$x_j$$$ can be the same as $$$y_j$$$, meaning that both ends of the road is city $$$x_j$$$.

Now the people on Planet E wants to build some stable for the horses. However the horses on Planet E has a strange habit: they must move exactly $$$k$$$ steps everyday. For each step, a horse must choose one of the roads that connects to its current city, and moves to the city on other end of the road. Hence we shall only build stables at city $$$i$$$ if a horse at city $$$i$$$ can move back to city $$$i$$$ after $$$k$$$ steps.

Can you help the people on Planet E to determine how many cities they can build stables at?

The first line contains a positive integer $$$T$$$ ($$$T \le 20$$$), the number of testcases.

Each testcase starts with a line consisting of three integers $$$n, m, k$$$ ($$$1 \le n \le 50$$$, $$$0 \le m \le 2500$$$, $$$0 \le k \le 10^9$$$), the number of cities and roads, and the number of steps a horse must move everyday. Then there are $$$m$$$ lines followed, each consisting of two integers $$$x_j, y_j$$$ ($$$0 \le x_j \le n - 1$$$, $$$0 \le y_j \le n - 1$$$), meaning that the $$$j$$$-th road connects city $$$x_j$$$ and city $$$y_j$$$.

For each testcase, output a single line consisting of the number of cities that can have a stable built.

3
3 2 3
0 1
0 2
3 2 4
0 1
0 2
5 5 5
0 1
1 2
2 0
3 4
4 0

0
3
4

In the last testcase, we can build stables at every cities but city $$$3$$$.

City $$$0$$$: $$$0 \to 1 \to 2 \to 0 \to 1 \to 0$$$.

City $$$1$$$: $$$1 \to 2 \to 0 \to 1 \to 2 \to 1$$$.

City $$$2$$$: $$$2 \to 0 \to 1 \to 2 \to 0 \to 2$$$.

City $$$4$$$: $$$4 \to 0 \to 1 \to 2 \to 0 \to 4$$$.