Đặc vụ

Hải đang chơi một trò chơi nhập vai, trong trò chơi này, anh vào vai một đặc vụ đang thực hiện nhiệm vụ xâm nhập vào một khu vực quân sự tuyệt mật. Khu vực này được mô phỏng bằng một hệ thống giao thông gồm \(n\) điểm kiểm soát, kết nối với nhau bằng các con đường hai chiều.

Tuy nhiên, hệ thống được bảo vệ nghiêm ngặt; khiến cho việc thực hiện nhiệm vụ của Hải diễn ra lâu hơn dự tính:

• Một số điểm kiểm soát có cài đặt khóa, có \(k\) loại khóa trên toàn hệ thống: nếu muốn vào phải có chìa khóa tương ứng.
• Một số điểm kiểm soát khác cất giữ chìa khóa. Hải có thể thu thập chìa khóa đó khi qua điểm kiểm soát tương ứng.

Ban đầu, trò chơi bắt đầu khi Hải tiến vào điểm kiểm soát số 1; trong tay anh không có bất kỳ chìa khóa nào. Mỗi khi đi qua một điểm kiểm soát:

• Nếu điểm đó không bị khóa, Hải có thể điều khiển nhân vật ra vào tự do.
• Nếu điểm đó có khóa loại \(x\), anh chỉ có thể vào nếu bạn đã sở hữu chìa khóa loại \(x\).
• Nếu tại điểm đó có chứa khóa loại \(y\), bạn sẽ nhận được chìa khóa và có thể dùng ngay tại bước kế tiếp.

Mục tiêu của trò chơi là thâm nhập vào một địa điểm trung tâm (có thể là một địa điểm bất kỳ trong hệ trạm kiểm soát), thông qua các con đường có sẵn. Mỗi lần vào chơi, điểm trung tâm lại thay đổi nên Hải cần tính toán thời gian ít nhất để di chuyển từ điểm kiểm soát \(1\) tới mỗi điểm kiểm soát khác.

Yêu cầu: Bạn hãy giúp Hải tính toán thời gian di chuyển nhé.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) (\(n \le 10^5, m \le 2 \times 10^5, k \le 5\)) là số địa điểm, số con đường và số loại khóa.

• Dòng thứ hai chứa n số nguyên \(a_1, a_2, ..., a_n\) (\(|a_i| \le k\)) mô tả về khóa tại các địa điểm: \(a_i = -1\) nếu tại điểm kiểm soát thứ \(i\) không có khóa, ngược lại là loại khóa được giữ tại đó.

• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, ..., b_n\) (\(|b_i| \le k\)) mô tả các địa điểm có cài đặt các loại khóa: \(b_i = -1\) cho biết tại điểm thứ \(i\) không cài đặt khóa nào, ngược lại là loại chìa khóa cần để vào điểm kiểm soát \(i\).

• \(m\) dòng tiếp, mỗi dòng gồm hai số nguyên dương \(u, v\) (\(u,v \le n\)) mô tả một đường nối giữa hai điểm kiểm soát \(u\) và \(v\).

Output

Một dòng gồm \(n\) số nguyên tương ứng là thời gian ít nhất để tới các điểm kiểm soát \(1,2,3,\ldots,n\) xuất phát từ địa điểm \(1\). Nếu không thể di chuyển từ \(1\) đến \(i\) thì tại vị trí \(i\) in ra \(-1\).

Example

5 4 2
-1 2 -1 1 -1
2 -1 -1 -1 1
1 2
1 3
2 4
3 5

0 1 1 6 2 

Scoring

• Có \(30\%\) số điểm của bài thỏa mãn không có khóa nào trên các đỉnh
• Có \(30\%\) số điểm khác thỏa mãn \(k = 1\)
• Còn lại không có điều kiện gì thêm