After Max and Alexis's initial plan to conquer the world with kitten armies failed, they started a new plan to conquer the kittenland. Currently, there are n cities in the world and m undirected roads which connect two cities. This time, Max and Alexis have placed one cat spy in each of the cities. Two cats can communicate with each other if it is possible to reach the city of one cat starting from the city of the other. Now Max is having fears that "hoomans" might destroy one of the cities so that some pairs of cats cannot communicate with each other. Now Max needs to know the number of pairs of cats who could communicate with each other before but would not be able to do that anymore if a particular city is destroyed. He needs to know this number for every city in the world. So Alexis has imprisoned you, the "hooman" programmer to solve this problem.
Input
In the first line the number of test cases, T will be given. For each test case, the first line will contain two integers, n and m, the number of cities and the number of roads in the world. Then m lines will follow each containing two integers u and v meaning there is a road between the city u and v.
**For all subtasks:
1<=T<=5
For Easy Subtask:
2 <= n <= 100
1 <= m <= 200
For Medium Subtasak:
2 <= n <= 1000
1 <= m <= 2000
For Hard Subtask:
2 <= n <= 100000
1 <= m <= 200000
**There will be no roads connecting one city to itself and all roads will be distinct.
Output
For each test case, print the case number in the first line in the same format as the sample output section. Then print n lines. The ith line should contain an integer which is the number of pairs of cats who will not be able to communicate anymore if the ith city is destroyed by the "hoomans".
Sample
| Input | Output |
|---|---|
2 3 2 1 2 2 3 7 7 1 2 2 3 3 4 4 5 1 3 4 6 6 7 | Case 1: 2 3 2 Case 2: 6 6 14 17 6 11 6 |
In the first test case, if "hoomans" destroy the first city, then the two cats at the other two cities will not be able to communicate with the cat at the first city. So the answer for the first city is two. Similarly, the answer for the third city is two too. For the second city, if we delete it, then no cat will be able to communicate with any other cat any more. So the answer is 3 here. The three pairs of cities are (1,2), (2,3) and (1,3).
