Giải bài trực tuyến

Có N học sinh và M trò chơi vi tính. Mỗi học sinh chỉ thích chơi một trò duy nhất và mỗi trò chơi có ít nhất một học sinh thích. Nhà trường tổ chức kết nối mạng LAN cho các máy trong Q phút, phút thứ i nối 2 máy của học sinh Ui và Vi ( coi như đồ thị vô hướng ). Tất cả những học sinh thích chơi cùng một loại game sẽ bắt đầu chơi khi máy tính của họ liên thông ( có thể đi qua các đỉnh chứa game khác ). Hỏi thời gian bắt đầu chơi của mỗi game.

Nếu game chỉ có 1 người thích thì sẽ bắt đầu vào phút thứ 0

Nếu 1 loại game không thế liên thông sau Q phút thì in ra -1 ứng với game đó

Input

Dòng 1: N, M, Q tương ứng với số học sinh, số trò chơi, số phút ( mỗi phút nối 1 dây LAN )
Dòng 2: Gồm N số A[i] miêu tả trò chơi mà học sinh thứ i thích
Q dòng tiếp theo: mỗi dòng gồm 2 số U[i] và V[i] 

Output

Gồm M dòng, dòng thứ i là thời điểm bắt đầu chơi của game thứ i

Example

Input:
5 2 4
1 2 2 2 1
1 2
2 3
1 5
4 5

Output:
3
4

Giới hạn: 

• 1 <= N, M <= 10^5.
• 0 <= Q <= 10^5