I try it using a BFS. Starting in a node with degree 1, setting the node as visited and its neighbors, adding in the queue the neighbors of neighbors of node. But, i was received only wrong answer with this strategy :(
Link for the problem: http://www.spoj.com/problems/IMPER/
sorry for my bad english.