Problem: Three planets X, Y and Z within the Alpha planetary system are inhabited with an advanced civilization. The spaceports of these planets are connected by interplanetary space shuttles. The flight scheduler should decide between 1, 2 and 3 return flights for every existing space shuttle connection. Since the residents of Alpha are strong opponents of the symmetry, there is a strict rule that any two of the spaceports connected by a shuttle must have a different number of flights. 

For every pair of connected spaceports, your goal is to propose a number 1, 2 or 3 for each shuttle flight, so that for every two connected spaceports the overall number of flights differs. 

You may assume that:

1) Every planet has at least one spaceport 

2) There exist only shuttle flights between spaceports of different planets 

3) For every two spaceports there is a series of shuttle flights enabling traveling between them

4) Spaceports are not connected by more than one shuttle

Input

The first row of the input is the integer number N (3 ≤ N ≤ 100 000), representing overall number of spaceports. The second row is the integer number M (2 ≤ M ≤ 100 000) representing number of shuttle flight connections. 

Third row contains N characters from the set \\{X, Y, Z\}. Letter on I^{th} position indicates on which planet is situated spaceport I. For example, "XYYXZZ" indicates that the spaceports 0 and 3 are located at planet X, spaceports 1 and 2 are located at Y, and spaceports 4 and 5 are at Z. 

Starting from the fourth row, every row contains two integer numbers separated by a whitespace. These numbers are natural numbers smaller than N and indicate the numbers of the spaceports that are connected. For example, "12\ 15" indicates that there is a shuttle flight between spaceports 12 and 15. 

Output

The same representation of shuttle flights in separate rows as in the input, but also containing a third number from the set \{1, 2, 3\} standing for the number of shuttle flights between these spaceports.

Example

Input


10
15
XXXXYYYZZZ
0 4
0 5
0 6
4 1
4 8
1 7
1 9
7 2
7 5
5 3
6 2
6 9
8 2
8 3
9 3


Output


0 4 2
0 5 2
0 6 2
4 1 1
4 8 1
1 7 2
1 9 3
7 2 2
7 5 1
5 3 1
6 2 1
6 9 1
8 2 3
8 3 1
9 3 1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
using ll = long long;
int n, m;
vector<int> v[N];
mt19937 e;
int sum[N], mp[3];
bool st[N], vis[N];
string s;
int rv(int x) { return 3 - (x % 3 + 3) % 3; }
vector<array<int, 3>> ans;
void dfs(int pos, int fa) {
  st[pos] = vis[pos] = 1;
  for (auto &i : v[pos]) {
    if (i == fa) continue;
    if (!vis[i]) {
      dfs(i, pos);
      int t = rv(sum[i] - mp[s[i] - 'X']);
      ans.push_back({pos, i, t});
      sum[pos] += t;
      sum[i] += t;
    } else if (st[i]) {
      sum[pos] += 3;
      sum[i] += 3;
      ans.push_back({pos, i, 3});
    }
  }
  st[pos] = 0;
}
bool solve() {
  mp[0] = 0;
  mp[1] = 1;
  mp[2] = 2;
  for (int i = 0; i < n; i++) shuffle(v[i].begin(), v[i].end(), e);
  shuffle(mp, mp + 3, e);
  memset(sum, 0, sizeof(sum));
  memset(vis, 0, sizeof(vis));
  int x = uniform_int_distribution<int>(0, n - 1)(e);
  ans.clear();
  dfs(x, -1);
  for (int i = 0; i < n; i++)
    for (auto &j : v[i])
      if (sum[i] == sum[j]) return 0;
  for (auto &i : ans) cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
  return 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> s;
  e.seed(time(0));
  for (int i = 1; i <= m; i++) {
    int t1, t2;
    cin >> t1 >> t2;
    v[t1].push_back(t2);
    v[t2].push_back(t1);
  }
  while (!solve())
    ;
  return 0;
}