8VC Venture Cup 2017 - Elimination Round |
---|
Закончено |
Польшар и его семья живут в лесу. Лес состоит из деревьев. Деревом называется неориентированный ациклический граф с k вершинами и k - 1 ребрами, где k — некоторое целое число. Заметьте, что изолированная вершина является корректным деревом.
В каждой вершине каждого дерева живет ровно один родственник, они пронумерованы от 1 до n. Для каждого шара i нам известен номер самого дальнего от него родственника, живущего на том же дереве. Если существует несколько таких родственников, нам известен лишь наименьший номер среди них.
Сколько же деревьев в лесу?
Первая строка содержит единственное целое число n (1 ≤ n ≤ 104) — число шаров, живущих в лесу.
Вторая строка содержит последовательность целых чисел p1, p2, ..., pn длины n (1 ≤ pi ≤ n), где pi означает номер самого дальнего от шара i родственника, живущего на том же дереве. Если существует несколько самых дальних родственников живущих на том же дереве, то pi — это номер того среди них, который имеет наименьший номер.
Гарантируется, что последовательность p соответствует некоторому корректному лесу.
Взломы: Чтобы взломать кого-либо, вы должны предоставить в качестве теста корректный лес. По этому лесу будет вычислена последовательность p и подана на ввод взламываемому решению. Используйте следующий формат:
В первой строке выведите целое число n (1 ≤ n ≤ 104) — число шаров, и целое число m (0 ≤ m < n) — число ребер в лесу. Далее, выведите m строк. Строка i должна содержать два целых числа ai и bi, отражающих наличие ребра между вершинами, в которых живут родственники ai и bi. Например, первый тест из условия должен быть выведен так:
5 3
1 2
3 4
4 5
Выведите число деревьев в лесу, где живет Польшар.
Технически данная задача является интерактивной. Однако, это никак не влияет на вас (кроме взломов), т. к. никакого взаимодействия нет.
5
2 1 5 3 3
2
1
1
1
В первом примере лес выглядит так: 1-2 3-4-5.
Всего здесь 2 дерева.
Во втором примере единственный возможный граф это одна вершина и ни одного ребра. Поэтому здесь всего одно дерево.
Название |
---|