Саша живет в большой дружной семье. В Мужской День мужчины из этой семьи собираются вместе и празднуют его, следуя своей особой традиции. В семье Саши n мужчин, поэтому для простоты будем нумеровать их от 1 до n.
Каждый мужчина имеет не более одного отца, но может иметь произвольное количество сыновей.
Мужчина с номером A является предком мужчины с номером B, если выполняется хотя бы одно из утверждений:
- A = B;
- мужчина с номером A — отец мужчины с номером B;
- существует такой номер C, что мужчина с номером A — предок мужчины с номером C, а мужчина с номером C — отец мужчины с номером B.
Конечно же, если мужчина с номером A является предком мужчины с номером B, причём A ≠ B, то мужчина с номером B не может являться предком мужчины с номером A.
На Мужской День в семье Саши принято дарить подарки. Просто так дарить подарки скучно, поэтому в этой семье процесс дарения каждый год выглядит следующим образом.
- Определяется список кандидатов, в котором перечислены некоторые из n мужчин в определённом порядке.
- Каждый из n мужчин решает сделать подарок.
- Чтобы сделать кому-нибудь подарок, мужчина выбирает из составленного списка первого члена семьи, который является его предком, и делает ему подарок. В частности, он может сделать подарок сам себе.
- Если в списке нет ни одного предка какого-нибудь мужчины, то он расстраивается и покидает праздник, так и не подарив никому подарок.
В этом году вы решили помочь с организацией праздника и узнали у каждого из n мужчин, кому из своих предков он хочет сделать подарок. Сможете ли вы построить список кандидатов таким образом, чтобы удовлетворить желание каждого?
Выходные данные
В первой строке выведите целое число k (1 ≤ k ≤ n) — количество мужчин в списке кандидатов.
Затем выведите k различных неотрицательных целых чисел — номера мужчин в списке кандидатов в порядке, определяющем необходимый выбор каждого из n мужчин, — по одному в строке.
Если подходящих списков несколько, выведите любой из них. Если подходящего списка не существует, выведите - 1 в единственной строке выходных данных.
Примечание
Пояснение к первому примеру:
- если в списке не будет 1, то желания первого и третьего мужчины не сбудутся (a1 = a3 = 1);
- если в списке не будет 2, то желание второго мужчины не сбудется (a2 = 2);
- если разместить в ответе 1 перед 2, то второму мужчине придется дарить подарок первому мужчине, а не себе (a2 = 2);
- если же разместить мужчину с номером 2 перед мужчиной с номером 1, то третьему мужчине придется дарить подарок второму мужчине, а не первому (a3 = 1).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2
2 3
1 2 1
|
-1
|
|
2
|
4 2
1 2
3 4
1 2 3 3
|
3
2
1
3
|