Sau khi nhập về một số lượng lớn bóng, ông \(Z\) đã lên kế hoạch phân phát bóng đến các gia đình đã đặt hàng.

Bản đồ thành phố nơi ông \(Z\) là một đồ thị vô hướng, có \(N\) đỉnh và \(M\) con đường đi. Cửa hàng ông \(Z\) ở đỉnh số \(1\), mỗi đỉnh còn lại sẽ đại diện cho một hộ gia đình. Có \(Q\) đơn đặc hàng, với mỗi đơn đặt hàng hãy giúp ông \(Z\) tính thời gian ngắn nhất để ông hoàn thành đơn hàng đó (biết sau khi hoàn thành bất kỳ đơn hàng nào ông sẽ về lại cửa hàng mình để nghỉ ngơi). Thời gian để đi lại giữa hai con đường là \(1\) giây.

Input

• Dòng đầu tiên gồm ba số $N,M,Q \ (N\leq20000,M\leq100000,Q\leq10000) $ - lần lượt là số hộ gia đình và số đường đi.

• \(M\) dòng tiếp theo mỗi dòng gồm \(2\) số \(u,v \ (1\leq u,v\leq N)\) - thể hiện có đường đi hai chiều giữ \(u\) và \(v\).

• \(Q\) dòng cuối mỗi dòng gồm một số $p \ (1\leq p\leq N) $ - là địa chỉ của hộ gia đình đặt hàng

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) là thời gian ngắn nhất để hoàn thành đơn hàng thứ \(i\). Dữ liệu luôn đảm bảo có đường đi.

Example

6 5 2

1 2

2 3

2 4

1 5

1 6

4 6 

2

1