Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIFBF - Facebook Friends(V1)

 

Given a graph G of N vertices and M edges representing the Facebook friendship in the EIUers community. Each vertex represents an EIU student, whose gender is Male or Female. Each edge represents the Facebook friends of two students.
The graph G forms a number of connected components (Connected Component - CC), with each CC selecting the vertex with the largest index as the representative vertex. Write a program that prints the representative peak, the number of males, the number of females for each CC.

Given a graph G of N vertices and M edges representing the Facebook friendship in the EIUers community. Each vertex represents an EIU student, whose gender is Male or Female. Each edge represents the Facebook friends of two students.

The graph G forms connected components, with each CC selecting the vertex with the largest index as the representative vertex. Write a program that prints the representative vertex, the number of males, the number of females for each component.

 

Input

The first line contains two integers N (0 <N ≤ 105) and M (0 ≤ M ≤ 3 * 105), respectively, the number of vertices and the number of edges of the graph. The vertices of the graph are numbered from 1 to N

The next line consists of N strings, each of which is "Nam" or "Nu", the corresponding i th string is the gender of the ith student.

The next M lines contain two numbers u and v, each representing u and v as Facebook friends

Output

Sort the connected components by the representation vertex, respectively print out the index of the representative. number of men, and number of women .

Example

Input:
6 6
Nam Nu Nu Nam Nam Nam
1 3
1 4
3 4
5 3
6 2
5 4

Output:
5 3 1
6 1 1

Added by:Ha Minh Ngoc
Date:2017-08-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.