Clarke and Australian Cricket Team
All submissions for this problem are available.
Michael Clarke is Secretary of the Australian Cricket Club. When the club gathers together, the players behave badly due to their bad performance in the Cricket World Cup 2015. They've brought lots of ropes to the club and got tied with each other. Specifically, each rope ties together two players. Also, if two players are tied together, then the rope connects the first player with the second one as well as the second player with the first one.
As Captain Clarke is already angry at their bad performance, this scenario got him more angrier. In his anger and frustration, Clarke does the following. First, for each player, Clarke finds out what other players he is tied to. If a player is tied to exactly one other player, Clarke reprimands him. Then Clarke gathers in a single group all the players who have been just reprimanded. He then throws them out from the club. This group of players immediately leaves the club. These players takes with them the ropes that used to tie them. Then again for every players Clarke finds out how many other players he is tied to and so on. And they do so until Clarke can reprimand at least one player. He doesn't even care if the club gets empty in the process.
Determine how many groups of players will be thrown out of the club.
The first line of input contains an integer T, denoting the number of test cases. Then T test cases are follow
The first line contains two integers n and m — the initial number of players and ropes. The players are numbered from 1 to n, and the ropes are numbered from 1 to m. Next m lines each contain two integers a and b — the numbers of players tied by the i-th rope (1 ≤ a, b ≤ n, a ≠ b). It is guaranteed that no two players are tied with more than one rope. No rope ties a player to himself.
Print the single number — the number of groups of players that will be thrown out from the club.
1 <= n <= 1000 <= m <= (n*(n-1))/2
1 ≤ a, b ≤ n, a ≠ b
Input: 1 3 3 1 2 2 3 3 1 Output: 0
Input: 1 6 3 1 2 2 3 3 4 Output: 2
Input: 1 6 5 1 4 2 4 3 4 5 4 6 4 Output: 1
In this case, Clarke won't throw out any group of players — in the initial position every player is tied to two other players and Clarke won't be able to reprimand anyone.
In this case, four players are tied in a chain and two more are running by themselves. First Clarke throw out the two players from both ends of the chain (1 and 4), then — two other players from the chain (2 and 3). At that the players who are running by themselves will stay in the club.
In the third sample, Clarke will momentarily kick out all players except for the fourth one and the process stops at that point. The correct answer is one.
|Tags||connected, easy, graph, prog_iitmandi|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.