Задача №2909. Функция Гранди
Пусть G=(V, E) – произвольный ориентированный граф. Для каждой вершины x этого графа введем множество Next(x) как множество всех вершин, в которые ведут дуги, выходящие из вершины x.
Пусть F – функция, принимающая целые неотрицательные значения, определенная на вершинах графа G. Функция F называется функцией Гранди, если для каждой вершины x графа G выполняется условие F(x)=min{n≥0|n≠F(y) ни для какой вершины y из Next(x)}.
Рассмотрим класс ориентированных графов, у которых в каждую вершину входит ровно одна дуга. Напишите программу, которая получает на вход некоторый граф из описанного выше класса и находит функцию Гранди для этого графа, если она существует.
Входной файл содержит описание ориентированного графа. В первой строке файла находится целое число N (2 ≤ N ≤ 100000), равное количеству вершин графа. В i-й из следующих N строк находится одно целое число Pi (1 ≤ Pi ≤ N; Pi ≠ i), равное номеру вершины, из которой выходит та дуга, которая ведет в вершину с номером i.
Eсли для графа, описанного во входном файле, не существует функции Гранди, то выходной файл должен содержать одну строку со словом "NO". В противном случае, файл должен состоять из N строк, в i-й из которых должно быть записано одно целое число Fi – значение найденной функции Гранди для вершины с номером i. Если существует несколько функций Гранди для графа, описанного во входном файле, то выведите любую из них.
4 2 4 4 1
YES
3 3 1 2
NO
4 4 3 2 1
YES