Perfect Matching with Even Black Edges

Given a bipartite graph with 2n vertices and m edges. The vertices in the left part are numbered 1 to n and the vertices in the right part are numbered n+1 to 2n. Each edge is colored either black or white. Your task is to find a perfect matching (i.e. a set of n edges such that every vertex is incident with exactly one edge from the matching) so that the number of black edges in the matching is even.

A bipartite graph is an undirected graph whose vertices can be divided into two disjoint sets, with each edge connecting one vertex from the left part to one from the right part. A perfect matching is a matching that matches all vertices.

If there are multiple valid answers, any one will be accepted. If no valid perfect matching exists, output -1.

inputFormat

The first line contains two integers n and m.

Each of the next m lines contains two integers u and v followed by a character c, where:

• u (1 ≤ u ≤ n) is a vertex from the left part,
• v (n+1 ≤ v ≤ 2n) is a vertex from the right part,
• c is either 'B' or 'W', representing black or white respectively.

outputFormat

If a valid perfect matching exists, output n space-separated integers. The i-th integer should be the vertex number (from the right part) that is matched with vertex i from the left. If no valid matching exists, output -1.

sample

2 4
1 3 B
1 4 W
2 3 W
2 4 B

3 4