UVA10735 混合图的欧拉回路 Euler Circuit

欧拉回路是指一个图上的回路，其恰好经过所有边一次。在有向图和无向图上寻找欧拉回路很简单，那么在一个有些边已定向而有些没有的图上呢？ 我们可以对没定向的边进行定向。然而，有时无论如何定向都无法使图上存在欧拉回路。 现在，给出一个这样的图，请判断是否存在一个合法的定向方案使得图上存在欧拉回路。若有，则按照特定格式输出该回路，若否请告知，详见输出格式。 若将所有边视为无向边，图保证联通。

第一行，一个整数 $T$，表示该测试点的数据组数。 对于每组数据： 第一行包含两个整数 $V$ 和 $E$，表示点数和边数。点数编号为 $1\sim V$。 接下来 $E$ 行，每行两个整数 $a,b$ 和一个大写字母 $type$，格式为 `a b type`，描述一条边。$a,b$ 为其端点；若 $type$ 为 $\texttt U$，则边未定向，若为 $\texttt D$ 则边方向为 $a\to b$。保证 $type$ 只会是二者之一。

对于每组数据： 若无论如何定向都没有欧拉回路存在，输出 $\texttt {No euler circuit exist}$。 若有，输出从起点开始的回路上的点编号。需要在开头结尾各输出一个起点编号，相邻两个点编号之间用一个空格隔开。可能有多种解，输出任意一个均可以通过。 **相邻两组数据间，需要输出一个额外空行。**

- $1\le T\le 20$ - $1\le V\le 100$ - $1\le E\le 500$