7178：Link with Level Editor II

Link is playing a game, called Advertising Space for Rent.

In this game, a level consists of several worlds. Each world consists of $m$ nodes and some directed roads. The player starts on node $1$ of the first world. In each world, the player can either stay at the current node or go through exactly one road that exists in that world. After that, the player will be teleported to the next world without changing the ID of the node where he stays. If there is no next world, the game ends. The player wins if he ends on node $m$.

Link is editing a new level, he has already made $n$ worlds (numbered from $1$ to $n$) and wants to choose a continuous subsegment of them to form a new level. The only limit is there shouldn't be more than $k$ ways to win. (Two ways are considered different if and only if the operation in some world differs.)

Link doesn't want to discard too many worlds. What is the maximum number of worlds Link can use in the new level?

Each test contains multiple test cases. The first line contains the number of test cases $T(1 \le T \le 30)$. Description of the test cases follows.

The first line contains three integers $n,m,k$ ($1 \leq n \leq 5 \times 10^3, 2 \leq m \leq 20, 1 \leq k \leq 10^9$).

The following input describes the worlds from $1$ to $n$. For each world:

The first line contains an integer $l$ ($0 \leq l \leq m \times (m-1)$), which is the number of roads in this world.

The next $l$ lines, each line contains two integers $u,v$ ($1 \leq u,v \leq m, u \neq v$), which means there is a road from node $u$ to node $v$ in this world.

For each world, it is guaranteed that there is no duplicate edge.

For each test case, it is guaranteed that the sum of $l$ does not exceed $10^6$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and the sum of $l$ over all test cases does not exceed $3 \times 10^6$.

For each test case, output a single integer, which is the maximum number of worlds Link can use in the new level.