Суффиксный автомат

Суффиксным автоматом для строки w называется детерминированный конечный автомат A, который допускает язык Suff(w) - множество суффиксов слова w. Например, суффиксный автомат для слова abbab должен допускать в точности следующие слова: {abbab, bbab, bab, ab, b, ε}. Мы также требуем, чтобы суффиксный автомат не имел недостижимых состояний, и не было состояний, из которых не достижимы допустимые. Других ограничений, например, минимальности, накладывать не будем.

На рисунке показан суффиксный автомат для слова abbab.

По заданному скелету суффиксного автомата некоторого слова требуется восстановить суффиксный автомат. А именно - вам даны состояния, переходы, начальное состояние и допускающие состояния. Но пометки на рёбрах удалены.

Вам следует расставить пометки на рёбрах заданного суффиксного автомата так, чтобы он стал суффиксным автоматом некоторого слова w, а также найти это слово. Для простоты будем считать, что размер алфавита ничем не ограничен, вы можете использовать в качестве символов числа от 1 до k (k вы можете выбрать сами).

Входные данные

Первая строка входного файла содержит три целых числа: n, m и t - количество состояний, количество переходов, и количество допускающих состояний, соответственно (2 ≤ n ≤ 200, 1 ≤ m ≤ 1000, 1 ≤ t ≤ n). Вторая строка содержит t целых чисел - номера допускающих состояний (состояния пронумерованы с 1, начальное состояние имеет номер 1).

Следующие m строк описывают переходы: каждая строка содержит два целых числа s_i и t_i и описывают переходы из s_i в t_i.

Выходные данные

На первой строке выходного файла выведите два целых числа l и k - длину слова w и размер алфавита. Используйте числа {1, ..., k} как элементы алфавита. k не должно превышать m.

Вторая строка должна содержать l целых чисел - слово w.

Наконец, третья строка должна содержать m целых чисел - метки на переходах скелета автомата, в том порядке, в каком они описаны во входном файле.

Гарантируется, что ответ всегда существует.

Примеры

Примечание