401488: GYM100482 H Real Magic

People like magic. Magic is powerful, interesting and mysterious. However, the real magicians are not more than talented cheaters. One of the most famous magicians is David Foolfield.

For example, suppose there is a room with a tied magician. Then the doors are closed, opened again - there is no magician and he appears in some other room. The thing we don’t know that there are secret doors that connect rooms with each other. Of course, he may use another cheap trick - to hide in the same room and his assistant that looks the same appears in the other room. However, we assume that there are no assistants in this problem.

We finally figured out the secret paths between the rooms. Now we want to calculate in how many rooms (other than the initial) the magician can appear. The magician can appear in any room which can be reached from the starting room directly or indirectly.

The first line contains the number of test cases T (T ≤ 30). The first line of each test case contains the number of rooms in the building n and the number of secret paths m (1 ≤ n, m ≤ 10⁴). The following m lines contains numbers a and b (1 ≤ a ≤ b ≤ n), meaning that rooms a and b are connected.

For each test case output one line containing “Case #tc:”, where tc is the number of the test case (starting from 1). Then output one additional line containing n numbers separated by spaces which show in how many rooms the magician can appear if he starts at the i-th room (for all i from 1 to n).

1
2 1
1 2

Case #1:
1 1