Shortest Distance to Nearest School

You are given a city network with n intersections labeled from 1 to n and a number of roads connecting them. Some intersections have schools, while others represent houses. The roads connect intersections and can be used to travel between them. It is possible that the network is not fully connected, and some intersections might be unreachable from any school.

Your task is to determine the shortest distance from each intersection to the nearest school. If an intersection is unreachable from any school, output -1 for that intersection.

The distance between two directly connected intersections is considered to be 1. Mathematically, if two intersections u and v are connected, then the distance is given by:

For each intersection i (from 1 to n), compute the distance to the nearest school.

inputFormat

The input is given from stdin and has the following format:

n k m
s1 s2 ... sk
u1 v1
u2 v2
... 
um vm

Where:

• n is the number of intersections.
• k is the number of schools.
• m is the number of roads.
• The second line contains k space-separated integers indicating the intersections that have schools.
• Each of the next m lines contains two integers u and v, indicating there is a bidirectional road between intersections u and v.

outputFormat

Print a single line to stdout containing n space-separated integers. The i-th integer represents the shortest distance from intersection i to the nearest school. If an intersection is unreachable from any school, print -1 for that intersection.

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

0 1 0 1 2