EIU Programming Practices and Exams

Ngan and her friend have just received their study result. Because their class is divided into groups, they want to know the highest score and lowest score of each group. Ngan’s friends are in the same group with Ngan. Anyone who is friend of at least one person in the group is also in the same group.

Input

The first line contains 2 integers n, m denotes the number of people and the number of friendships (0 ≤ n, m ≤ 2 * 10⁵). Each person is numbered from 0 to n - 1.

The ith real number in the next line represents the score of the ith person.

Each line in the next M lines contains two numbers u and v, denoting u and v as friends.

Output

For each group, ordered in ascending of representative (the smallest index in the group), print out the highest score and lowest score.

Sample