D. Traffic Lightstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output 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$$$. InputEach 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$$$.OutputFor 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.ExampleInput26 61 22 33 44 61 55 64 31 21 31 4Output4 2
3 0
NoteIn 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 case, an optimal strategy is to do the following: at time $$$0$$$, move the token from vertex $$$1$$$ to vertex $$$2$$$, at time $$$1$$$, move the token from vertex $$$2$$$ to vertex $$$1$$$, at time $$$2$$$, move the token from vertex $$$1$$$ to vertex $$$4$$$.