EIU Programming Practices and Exams

Mạng xã hội thường tìm cách để xuất cho người dùng những người bạn mà họ có thể quen biết. Phúc vừa đề xuất giải pháp để xác định hai người có thể quen biết hay không: nếu a, b sống cùng địa phương và có ít nhất một bạn chung thì a và b có thể quen nhau. Biết thông tin nơi sống các người dùng và mối quan hệ bạn bè, với mỗi người hãy cho biết họ có thể quen bao nhiều người mà họ chưa kết bạn.

Input

Dòng đầu tiên là hai số nguyên nlà số người dùng trên mạng xã hội và số mối quan hệ xã hội (0 < n ≤ 10⁵, 0 < m ≤ 2 * 10⁵). Mỗi người được đánh mã số từ 0 đến n – 1.

Dòng tiếp theo gồm n số nguyên lần lượt là địa phương sống của n người.

m dòng tiếp theo, mỗi dòng gồm hai số nguyên a và b thể hiện a và b là bạn của nhau.

Output

Gồm n dòng, mỗi dòng là mã số người dùng và số người mà họ có thể quen. Kết quả được sắp xếp theo mã số người dùng tăng dần.

Example

Input:
5 6
1 2 2 1 1
0 1
0 2
1 3
2 3
2 4
3 4


Output:
0 2
1 1
2 1
3 1
4 1