Spanning tree

[StTwister]

Hi,

Given a unweighted bidirectional graph, each edge labeled a positive integer (there can be more edges with the same label), how can I determine a spanning tree of the graph (if possible) that doesn't have more edges with the same label.

Can anyone point me towards a solution/algorithm?

[msg555]

Are you looking for a polynomial time algorithm. How many verticies are there? Are edges with common labels common?

[StTwister]

Yes, i'd prefer a polynomial algorithm if possible.

Both edges and vertices are at most 200.

If 2 edges have the same label, then they cant be in the spanning tree at the same time. So the spanning tree should contain N-1 different labels, where N is the number of vertices.