Odlama

Sizin qarşınızda ən sadə tor var. Lakin təcrübəli olimpiadçı kimi Siz müəyyən etdiniz ki, o $n$ təpəsi və $m$ tili olan əlaqələndirilmiş qrafdır. Əgər hər hansı bir təpəyə od vurarsınızsa, onda o yanar, bir saniyədən sonra ona qonşu olan bütün təpələr də yanar, daha sonra isə onlara qonşu olan təpələr yanar və s.

Sizə torun hansı təpələrinə od vurulacağı məlumdur (hamısına eyni zamanda). Sonuncu təpənin odlanması üçün neçə dəqiqə keçəcəyini və bunun hansı təpə olacağını bilmək tələb olunur.

Giriş verilənləri

İlk sətirdə natural $n(1\le n\le 10^5)$ və $m(n-1\le m\le 10^5)$ ədədləri verilir. Sonra tillərin sonu olan təpələrin nömrəsini ifadə edən hər birində iki ədəd olan $m$ sətir verilir. Təpələr $1$-dən başlayaraq nömrələnir.

Növbəti sətirdə od vurulan nöqtələrin sayını ifadə edən $k(1\le k\le n)$ ədədi verilir. Növbəti sətirdə od vurulan təpələrin nömrələrini ifadə edən $k$ ədəd verilir.

Çıxış verilənləri

İlk sətirdə sonuncu təpənin odlanacağı zamanı verin. İkinci sətirdə bu təpənin nömrəsini verin. Əgər belə təpələrin sayı bir neçə olarsa, onlardan nömrəsi kiçik olanı verin.

Nümunələr