# Euler Circuit

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 2 68 13U 14U 24U 25D 34D 45U 56D 56U 44 12D 14D 23U 34U Sample Output 134256541

2/2 No euler circuit exist