Monopoly Game Minimum Turns

You are given a simplified version of the Monopoly board game. The board is represented as a sequence of spaces, starting from space 1. In one turn, a player rolls a die which yields an integer from \(1\) to \(6\) (inclusive). The player then moves forward that many spaces.

Some spaces on the board are marked as teleportation spaces. If a player lands on a teleportation space \(P\), they are immediately transported to another space \(T\). The teleportation rule is defined by a mapping \(P \to T\). Note that a move could both advance by a die roll and then trigger a teleportation.

The objective is to compute the minimum number of turns required to reach or exceed a given target space number \(N\). You will be given \(T\) test cases. For each test case, the first line has two integers: the target space \(N\) and the number of teleportation rules \(M\). This is followed by \(M\) lines, each containing two integers \(P\) and \(T\), which represent the teleportation from space \(P\) to space \(T\).

Use breadth-first search (BFS) to explore the valid moves, considering die rolls from \(1\) to \(6\) and applying teleportation if the move lands on a teleportation space. The problem guarantees that a solution exists for each test case.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
N1 M1
P1,1 T1,1
P1,2 T1,2
... (M1 lines)
N2 M2
... (and so on for T test cases)

Here, T is the number of test cases. For each test case, the first line contains two space-separated integers: the target board space \(N\) and the number of teleportation rules \(M\). Each of the following \(M\) lines contains two integers \(P\) and \(T\) representing a teleportation from space \(P\) to space \(T\>.

outputFormat

For each test case, print the minimum number of turns required to reach or exceed space \(N\) on a separate line. The output should be written to standard output (stdout).

1
15 2
3 10
9 14

2