描述:

  小明正在一个神奇的地方旅游,这里有n个城市,有m条双向道路,每条道路连接两个城市,且不存在环,即不会有两条不同的简单路径连通两个城市u和v。

  小明希望选择一个城市,并且从这个城市开始沿着道路访问至少k个不同的城市(一开始选择的那个城市也算是一个被访问的城市)。走过一条道路需要花费1个单位的时间,小明希望花费的时间尽量少。

  你能帮助他吗?

   

输入:

  第一行两个整数n和m,表示有n个城市,m条道路。

  接下来m行每行两个整数u、v表示第u个城市和第v个城市之间有一条道路。

  接下来一行一个整数q,表示有q组询问。

  接下来q行每行一个整数k,问选择一个城市,并沿着道路访问至少k个不同的城市的最短时间。

  

输出:

  对于每组询问,输出一行表示最短的时间,如果无法访问至少k个不同的城市,请输出”impossible”,注意不要输出引号。

 

样例输入:

2 1 

1 2 

3

 

样例输出:

impossible

 

范围:

  1<=n<=10^5,0<=m<n,1<=q<=10^5,1<=k<=10^5。

  保证数据有梯度。