You are given a simple undirected connected graph of (n) vertices and (m) edges. There is a token in vertex (1). We consider the initial time to be at (0) seconds. After (t) seconds, if the token is in vertex (u), you must do exactly one of the following: wait one second, move the token through the ((t \bmod \mathrm{deg}(u) + 1))(^{\text{∗}})-th edge of (u), which takes one second. The order of edges of a vertex is the order that they appear in the input. Calculate the minimum time required to move the token from vertex (1) to vertex (n), and the minimum time spent waiting that can be achieved while minimizing the total time. (^{\text{∗}})(x \bmod y) denotes the remainder from dividing (x) by (y). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 1000)). The description of the test cases follows. The first line of each test case contains two integers (n), (m) ((2 \leq n \leq 5000), (n - 1 \leq m \leq \frac{n(n - 1)}{2})) — the number of vertices and edges in the graph, respectively. Then (m) lines follow, the (i)-th line containing two integers (u_i) and (v_i) ((1 \leq u_i, v_i \leq n)) — the vertices of the (i)-th edge. It is guaranteed that the graph is connected and simple. It is guaranteed that the sum of (n) over all test cases does not exceed (5000), and the sum of (m) over all test cases does not exceed (5\cdot 10^5). For each test case, output a single line containing two integers — the minimum total time and the minimum waiting time that minimizes the total time, respectively. In the first test case, an optimal strategy is to do the following: at time (0), wait one second, at time (1), move the token from vertex (1) to vertex (5), at time (2), wait one second, at time (3), move the token from vertex (5) to vertex (6). In the second test c