Чтобы как можно быстрее узнавать последние новости о своей любимой принципиально новой операционной системе, BolgenOS community Нижнего Тагила решило разработать схему, согласно которой первый член community, узнавший какую-либо новость, звонит кому-то другому, тот звонит третьему и так далее. То есть человеку с номером i был назначен человек с номером fi, которому он должен звонить, как только сам узнает новость. Со временем участники BolgenOS community поняли, что их схема не всегда срабатывает — некоторые могут так и не узнать новость. Теперь они хотят дополнить ее: в схему добавляется несколько указаний вида (xi, yi), означающих, что человек xi должен позвонить еще и человеку yi. Какое наименьшее число указаний нужно добавить, чтобы, независимо от того, кто первый узнал новость, в итоге новость узнали все?
Выходные данные
В первую строку выходных данных выведите одно число — какое наименьшее число указаний нужно добавить. Далее выведите один из возможных вариантов добавления этих указаний в схему, по одному указанию в строке. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3 2
|
1
3 1
|
|
2
|
7
2 3 1 3 4 4 1
|
3
2 5
2 6
3 7
|