#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N, M;
	cin >> N >> M;

	int A[1001], B[1001];
	char C[1001];
	rep(i, M) {
		cin >> A[i] >> B[i] >> C[i];
		A[i]--;
		B[i]--;
	}
	vector<int> E[1000010];
	rep(i, M) rep(j, M) {
		if (C[i] != C[j]) continue;
		if (i == j) continue;

		E[A[i] * N + A[j]].pb(B[i] * N + B[j]);
		E[A[i] * N + B[j]].pb(B[i] * N + A[j]);
		E[B[i] * N + A[j]].pb(A[i] * N + B[j]);
		E[B[i] * N + B[j]].pb(A[i] * N + A[j]);
	}

	int D[1000100] = {};
	rep(i, N* N) D[i] = 1e9;

	queue<int> que;
	que.push(N - 1);
	D[N - 1] = 0;
	while (que.size()) {
		int u = que.front();
		que.pop();

		for (auto to : E[u]) {
			if (D[to] < 1e8) continue;
			chmin(D[to], D[u] + 1);
			que.push(to);
		}
	}

	//if (D[(N - 1) * N] > 1e8) co(-1);
	//else co(D[(N - 1) * N]);

	int kotae = 1e9;
	rep(i, N) chmin(kotae, D[i * N + i] * 2);
	rep(i, M) chmin(kotae, D[A[i] * N + B[i]] * 2 + 1);
	rep(i, M) chmin(kotae, D[B[i] * N + A[i]] * 2 + 1);

	if (kotae > 1e8) co(-1);
	else co(kotae);

	Would you please return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	string t = "";
	cin >> s;
	int f = 1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R') f *= -1;
		else if (f == 1) {
			if (*t.end() == s[i]) t.pop_back();
			else t.push_back(s[i]);
		}
		else if (f == -1) {
			if (*t.begin() == s[i]) t.erase(0, 1);
			else t = s[i] + t;
		}
	}
	if (f == -1) reverse(t.begin(), t.end());
	for (int i = 0; i < t.size() - 1; i++) {
		if (t.size() == 0) break;
		while (t[i] == t[i + 1] && t.size()) {
			t.erase(i, 2);
			if (i > 0) i--;
		}
	}
	cout << t << endl;
}