После того как Скотланд-Ярд не справился с расследованием череды убийств, на помощь позвали Шерлока Холмса.
Собрав улики, оставленные на местах преступления, великий сыщик понял, что все убийства совершены одним человеком, а все убитые были его знакомыми.
Холмсу известны все пары людей, которые были знакомы друг с другом до совершения первого убийства. Также он знает, что на похороны к погибшему приходили все его знакомые, включая убийцу, и знакомились там друг с другом. Известно также, что убийца не совершал новых убийств до окончания похорон своей предыдущей жертвы.
Определите достаточно ли у Шерлока Холмса информации, чтобы однозначно определить убийцу, и день, после которого череду преступлений можно было остановить, арестовав его.
В первой строке задано количество людей N (2 ≤ N ≤ 105) и число пар знакомых M (1 ≤ M ≤ min(2 × 105, N × (N - 1) / 2)).
Далее следуют M строк с описанием пар знакомых Ui и Vi (1 ≤ Ui, Vi ≤ N, Ui ≠ Vi) до совершения первого убийства. Все пары знакомых различны.
В следующей строке задано количество дней T (1 ≤ T ≤ N - 1).
В последней строке заданы T чисел Ai — номер человека, убитого в i-й день.
Выведите два числа — номер дня, после которого можно однозначно идентифицировать убийцу, и его идентификатор. Дни и идентификаторы людей нумеруются с 1.
Если идентифицировать убийцу невозможно, выведите -1.
4 3
1 2
1 3
4 3
2
1 4
2 3
5 4
1 2
3 1
1 4
5 4
3
1 4 5
-1
6 6
1 2
2 3
3 4
4 5
5 2
2 6
4
2 4 6 5
4 3
