EIU Programming Practices and Exams

Given a graph that describes a social network with n members (n <= 10^5).

Every node is a member, every edge is the friendship between two members. Given member u, we call a set f(k, u) is k-level friends of member u, in other words, they are members who have the shortest path to member u equal to k. Special cases:

• f(1, u) is the set of friends of member u
• f(2, u) is the set of members who are not friends with member u, but they are friends to member u's friends.

Input:

• First line contains two integers n and m, the number of nodes and edges respectively
• Next m lines each contains two integers u and v, denoting an edge of the graph
• The next line is the integer u
• The following line has one integer q, number of queries (0<q<n)
• The last line contains q distinct integers ki(0<=ki<n)

Output:

For each query, print out in one line the set of nodes which are ki-level friends with member u, the nodes in the set are ordered increasingly by id and white-space separated.

Print out -1 if cannot find any ki-level friends of member u

Sample:

Input:

4 3

0 3

1 2

2 3

2

2

3

1

Output:

-1

1 3