CF2122D Traffic Lights

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 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 $ .