D. Подарки по списку
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Саша живет в большой дружной семье. В Мужской День мужчины из этой семьи собираются вместе и празднуют его, следуя своей особой традиции. В семье Саши n мужчин, поэтому для простоты будем нумеровать их от 1 до n.

Каждый мужчина имеет не более одного отца, но может иметь произвольное количество сыновей.

Мужчина с номером A является предком мужчины с номером B, если выполняется хотя бы одно из утверждений:

  • A = B;
  • мужчина с номером A — отец мужчины с номером B;
  • существует такой номер C, что мужчина с номером A — предок мужчины с номером C, а мужчина с номером C — отец мужчины с номером B.

Конечно же, если мужчина с номером A является предком мужчины с номером B, причём A ≠ B, то мужчина с номером B не может являться предком мужчины с номером A.

На Мужской День в семье Саши принято дарить подарки. Просто так дарить подарки скучно, поэтому в этой семье процесс дарения каждый год выглядит следующим образом.

  1. Определяется список кандидатов, в котором перечислены некоторые из n мужчин в определённом порядке.
  2. Каждый из n мужчин решает сделать подарок.
  3. Чтобы сделать кому-нибудь подарок, мужчина выбирает из составленного списка первого члена семьи, который является его предком, и делает ему подарок. В частности, он может сделать подарок сам себе.
  4. Если в списке нет ни одного предка какого-нибудь мужчины, то он расстраивается и покидает праздник, так и не подарив никому подарок.

В этом году вы решили помочь с организацией праздника и узнали у каждого из n мужчин, кому из своих предков он хочет сделать подарок. Сможете ли вы построить список кандидатов таким образом, чтобы удовлетворить желание каждого?

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

В первой строке входных данных записаны два числа n и m (0 ≤ m < n ≤ 100 000) — число мужчин в семье и число родственных связей.

В следующих m строках описываются родственные связи: в (i + 1)-й строке содержится пара чисел pi и qi (1 ≤ pi, qi ≤ n, pi ≠ qi), означающая, что мужчина с номером pi является отцом мужчины с номером qi. Гарантируется, что никакая пара чисел не встречается более одного раза, что для любых двух различных членов семьи хотя бы один из них не является предком другого и что никакой член семьи не имеет более одного отца.

В следующей строке дана последовательность n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n), i-е число в которой обозначает, что мужчина с номером i хочет сделать подарок мужчине с номером ai. Гарантируется, что для всех 1 ≤ i ≤ n мужчина с номером ai является предком мужчины с номером i.

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

В первой строке выведите целое число k (1 ≤ k ≤ n) — количество мужчин в списке кандидатов.

Затем выведите k различных неотрицательных целых чисел — номера мужчин в списке кандидатов в порядке, определяющем необходимый выбор каждого из n мужчин, — по одному в строке.

Если подходящих списков несколько, выведите любой из них. Если подходящего списка не существует, выведите  - 1 в единственной строке выходных данных.

Примеры
Входные данные
3 2
1 2
2 3
1 2 1
Выходные данные
-1
Входные данные
4 2
1 2
3 4
1 2 3 3
Выходные данные
3
2
1
3
Примечание

Пояснение к первому примеру:

  • если в списке не будет 1, то желания первого и третьего мужчины не сбудутся (a1 = a3 = 1);
  • если в списке не будет 2, то желание второго мужчины не сбудется (a2 = 2);
  • если разместить в ответе 1 перед 2, то второму мужчине придется дарить подарок первому мужчине, а не себе (a2 = 2);
  • если же разместить мужчину с номером 2 перед мужчиной с номером 1, то третьему мужчине придется дарить подарок второму мужчине, а не первому (a3 = 1).