I. Цепочки

Задачу добавил: alef

Успешно сдано решений: 29

Ограничение по времени: 2 с

Ограничение по памяти: 256 Мб

Министр экономики Калистрат тоже простое предложение внёс: уже сейчас во всём дворце можно заменить обычные лампы энергосберегающими, которые на движение реагируют. Входит человек в залу или какое другое помещение — лампы включаются. А если нет никого — то освещение не нужно. Вот в коридоре, ведущем в большую залу, неделю назад энергосберегающие лампы появились — разве не красота?

Тут ему казначей Ферапонт возразил: в коридоре пальмы стоят, естественного освещения им не хватает, а тут и искусственного их лишили. Теперь приходится думать, куда пальмы переставить, а это не так просто сделать. В коридоре смонтирована система автополива, а смонтировать такую систему не везде получится: коммуникации не позволят. А уж переложить коммуникации — очень непростая задача...

Конечно, министр экономики Калистрат знает о том, что внедрение какого-либо новшества может потребовать внедрения какого-то другого новшества и так далее. Однако его желание внедрить новшества очень велико, так что Ферапонту остаётся только оценивать, к каким последствиям внедрения этих новшеств приведут.

Министр Калистрат желает внедрить $n$ новшеств. Для внедрения каждого новшества может потребоваться внедрение какого-либо другого (но только одного) новшества. Будем называть такое новшество предшественником. Конечно, есть новшества, которым предшественники не требуются.

Таким образом, новшества могут образовывать цепочки. Цепочка начинается с новшества, которое не имеет предшественника. Затем в цепочке следует новшество, для которого первое новшество является предшественником, и т.д.

Ваша задача — разбить все новшества на минимальное количество цепочек и определить состав этих цепочек.

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

В первой строке содержится целое число $n$ $(1 \leq n \leq 3 \cdot 10^{5})$ — количество новшеств.

Во второй строке содержится $n$ целых чисел $p_{1}, p_{2}, \dots, p_{i}$ $(0 \leq p_{i} \leq n, i = 1, 2, \dots, n)$ , $p_{i}$ — номер новшества, являющегося предшественником новшества $# i$ . Если новшеству $# i$ не требуется предшественник, $p_{i} = 0$ .

Гарантируется, что каждое новшество является предшественником не более одного другого новшества.

Также гарантируется, что описанные взаимосвязи новшеств не образуют циклических зависимостей.

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

В первой строке выведите целое число $k$ — минимальное количество цепочек, на которые можно разбить все новшества.

Каждая из следующих $k$ строк содержит длину цепочки $l_{j}$ $(j = 1, 2, \dots, k)$ , за которой следует $l_{j}$ чисел — номера новшеств в цепочке в порядке их реализации. Разделяйте числа пробелами.

Порядок вывода цепочек не важен.

Пример

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

10
2 0 9 8 0 4 5 3 0 7

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

3
2 2 1 
3 5 7 10 
5 9 3 8 4 6

Сдать задачу

Задать вопрос жюри по этой задаче

Login:
Password:
	Забыли пароль?