Problem D
Euler
Circuit
Input: standard input
Output: standard output
Time Limit: 2 seconds
An
Euler circuit is a graph traversal starting and ending at the same vertex and
using every edge exactly once. Finding an Euler circuit in an undirected or
directed graph is a fairly easy task, but what about graphs where some of the
edges are directed and some undirected? An undirected edge can only be traveled
in one direction. However, sometimes any choice of direction for the undirected
edges may not yield an Euler circuit.
Given
such a graph, determine whether an Euler circuit exists. If so, output such a
circuit in the format specified below. You can assume that the underlying
undirected graph is connected.
Input
The first line in the input
contains the number of test cases, at most 20.
Each test case starts with a line containing two numbers, V
and E:
the number of vertices (1 <= V <= 100) and
edges (1
<= E <= 500) in the graph. The vertices
are numbered from 1 to V.
Then follows E
lines specifying the edges. Each such line will be in the format a b type
where a
and b
are two integers specifying the endpoints of the edge. type will either
be the character 'U',
if the edge is undirected, or 'D', if the edge is directed. In
the latter case, the edge starts at a and
ends at b.
Output
If an
Euler circuit exist, output an order in which the vertices can be traversed on
a single line. The vertex numbers should be delimited with a single space, and
the start and end vertex should be included both at the beginning and the end
of the sequence. Since most graphs have multiple solutions, any valid solution
will be accepted. If no solution exist, output the line "No euler circuit
exist". Output a blank line between each test case.
Sample Input Output for Sample Input
|
2
6 8
1 3 U
1 4 U
2 4 U
2 5 D
3 4 D
4 5 U
5 6 D
5 6 U
4 4
1 2 D
1 4 D
2 3 U
3 4 U
|
1 3 4 2 5 6
5 4 1
No euler circuit
exist
|
Problem setter: Jimmy Mårdell, Member of
Elite Problemsetters' Panel