{"raw_statement":[{"iden":"statement","content":"On Planet E, people travel by horses!\n\nThere 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$.\n\nNow 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.\n\nCan you help the people on Planet E to determine how many cities they can build stables at?\n\nThe first line contains a positive integer $T$ ($T <= 20$), the number of testcases.\n\nEach testcase starts with a line consisting of three integers $n, m, k$ ($1 <= n <= 50$, $0 <= m <= 2500$, $0 <= k <= 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 <= x_j <= n -1$, $0 <= y_j <= n -1$), meaning that the $j$-th road connects city $x_j$ and city $y_j$.\n\nFor each testcase, output a single line consisting of the number of cities that can have a stable built.\n\nIn the last testcase, we can build stables at every cities but city $3$.\n\nCity $0$: $0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 0$.\n\nCity $1$: $1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 1$.\n\nCity $2$: $2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 2$.\n\nCity $4$: $4 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 4$.\n\n"},{"iden":"input","content":"The first line contains a positive integer $T$ ($T <= 20$), the number of testcases.Each testcase starts with a line consisting of three integers $n, m, k$ ($1 <= n <= 50$, $0 <= m <= 2500$, $0 <= k <= 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 <= x_j <= n -1$, $0 <= y_j <= n -1$), meaning that the $j$-th road connects city $x_j$ and city $y_j$."},{"iden":"output","content":"For each testcase, output a single line consisting of the number of cities that can have a stable built."},{"iden":"note","content":"In the last testcase, we can build stables at every cities but city $3$.City $0$: $0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 0$.City $1$: $1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 1$.City $2$: $2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 2$.City $4$: $4 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 4$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ V = \\{0, 1, \\dots, n-1\\} $ and $ E \\subseteq V \\times V $, where each edge $ (x_j, y_j) \\in E $ represents a bidirectional road. Let $ A \\in \\{0,1\\}^{n \\times n} $ be the adjacency matrix of $ G $, with $ A_{i,j} = 1 $ if $ (i,j) \\in E $, else $ 0 $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 50 $  \n2. $ 0 \\leq m \\leq 2500 $  \n3. $ 0 \\leq k \\leq 10^9 $  \n4. $ T \\leq 20 $  \n\n**Objective**  \nFor each test case, compute the number of cities $ i \\in V $ such that there exists a walk of exactly $ k $ steps starting and ending at $ i $. This is equivalent to computing the number of indices $ i $ for which $ (A^k)_{i,i} > 0 $.  \n\nOutput:  \n$$\n\\left| \\left\\{ i \\in \\{0, 1, \\dots, n-1\\} \\mid (A^k)_{i,i} > 0 \\right\\} \\right|\n$$","simple_statement":"Count how many cities allow a horse to return to the same city after exactly k steps, moving along roads each step.","has_page_source":false}