Look at my solution in my profile page.
I have the same algorithm, but I didn’t use any graph traversal, it wasn’t needed.
Your code comments are very funny… 
best comment i have ever seen…
also, tweet about them
I have implemented the same. This is sample code for it incase anyone wants a reference.
Solution : CodeChef: Practical coding for everyone
Haha 
Just wanted to make coding a bit fun
Check this test case out
1
7 9
1 2
2 3
3 4
4 1
1 3
2 4
5 7
5 6
6 7
One of the correct answer is
2
1 2 2 2 2 2 2
Your solution gives
3
1 1 1 1 3 1 2
keep it up bro… its gives a smile to our faces