Để tham gia được tại sân chơi rộng lớn là OLP-ICPC, các chiến binh của UMT đã khổ luyện ngày đêm. Ngoài việc tham gia các khoá học online, các bạn còn cùng nhau tổ chức các chương trình codecamp thật bổ ích. Vậy đó là gì?

Codecamp là một hoạt động không thể thiếu của các coder competitive programming tại UMT. Đó là dịp mà các bạn sẽ tách khỏi trường, đi đến một nơi thật xa, và chỉ để code. Có lần thì đi ra cảng Cát Lái ngắm hoàng hôn, có lần đi Vũng Tàu bắt cá, hoặc ra tận Huế để để vừa ngắm sông Hương vừa code, ... Và trong một chuyến codecamp như thế của CLB lập trình UMT, các thành viên thuê xe máy để đi tham quan các địa điểm. Có tất cả ~n~ địa điểm để thăm và giữa chúng có ~m~ con đường một chiều cho xe máy chạy qua được (nghĩa là có đường đi từ ~A~ đến ~B~ thì chưa chắc có đường từ ~B~ về ~A~), trong đó có ~k~ địa điểm có phục vụ ăn uống. Các coder của UMT muốn xen kẽ giữa chuyến đi chơi sẽ có các buổi ăn uống, thư giãn. Vì thế các coder muốn biết rằng từ mỗi địa điểm trong ~n~ địa điểm thì khoảng cách ngắn nhất đến một địa điểm ăn uống nào đó là bao nhiêu (khoảng cách ở đây là số con đường một chiều mà bạn ấy cần phải đi qua).

Input

Dòng đầu tiên gồm các số ~n~, ~m~, ~k~ cho biết số địa điểm, số đường đi và số địa điểm đặc biệt, trong đó ~2 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^6~ (các đường đi có thể bị lặp lại) và ~0 ≤ k ≤ n~. Dòng thứ hai gồm danh sách các địa điểm ăn uống, mỗi giá trị sẽ từ 1 đến ~n~, phân biệt nhau. Trong m dòng tiếp theo sẽ có các thông tin con đường đi giữa từ địa điểm ~u → v~ nào đó với ~1 ≤ u \neq v ≤ n~

Output

Một dòng duy nhất gồm n khoảng cách từ địa điểm 1, 2, ..., ~n~ đến chỗ có thể ăn uống gần nhất. Với mỗi địa điểm không đi được thì in ra -1.

Sample Input 1

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

Sample Ouput 1

0 3 2 1 0

Sample Input 2

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

Sample Ouput 2

0 1 -1 -1 0

Giải thích

Trong Ví dụ 1, ta thấy địa điểm 1, 5 đã là đặc biệt nên không cần di chuyển gì, còn từ địa điểm 2, 3, 4 có thể đi đến địa điểm 5 với độ dài đường đi lần lượt là 3, 2, 1; trong Ví dụ 2, ta thấy tương tự trên nhưng địa điểm 2 đến được địa điểm 1 qua 1 bước, còn địa điểm 3, 4 thì không đến được 1 hoặc 5 bằng cách nào cả..

Subtask:

• Subtask 1 (50% số điểm): ứng với ~n ≤ 10~.

• Subtask 2 (15% số điểm): ứng với ~10 < n ≤ 1000~.

• Subtask 3 (35% số điểm): Không giới hạn gì thêm.