I take the list (any City with 1 road) and delete this road, then going to connected city and mark all road from it as non-delete, then  i going to near city and repeat first step.
For example
5 4
1 2
2 3
3 4
3 5
Start with 1 City, delete (1 2) then go in 3 city, and remove (3 4) or (3 5)?

Why WA2 ?
Sorry fo my English.

here is example:
8 7
1 2
2 3
3 4
3 5
4 7
7 8
5 6

Answer depends on the way you go from city 3.

Yes.
But your algorithm probably realy work wrong.
My greedy:
While graph is not empty
1. We choose any vertex v: deg(v)=1 (e=(v,u))
2. Add to the answer edge e.
3. Delete v and u with all its edges from the graph.

why gredy is correct?

@Burunduk1
I used the same greedy algorithm as u did but I get WA#2, can u please help me?

Edited by author 24.07.2013 17:16