Дитячий садок#6837
Щороку троє дружніх виховательок дитячого садка дозволяють дітям зі своїх груп змінювати класи, щоб сформувати три нових. Деякі діти, звісно, вже достатньо дорослі, щоб піти, але ті, хто залишаються ще на рік, перерозподіляються між трьома виховательками.
Виховательки навіть дозволяють дітям висловити свою думку під час цього процесу. Оскільки дружба у юному віці часто швидко з'являється і зникає, кожна дитина ранжує всіх інших дітей відповідно до того, наскільки була б рада бачити у своєму новому класі. Насправді, створює список уподобань, що задає повний порядок інших дітей, тобто у списку не може бути однаково бажаних дітей — неможливі «нічиї», всі діти мають бути впорядковані строго по пріоритету.
Трьох виховательок не турбує, якщо нові класи будуть різними за розміром, оскільки вони все одно набирають дітей, що розпочнуть свій перший рік у садку. Проте вони хочуть, щоб у їхньому новому класі не було жодної дитини з їхнього минулорічного складу, адже навіть виховательці потрібна перерва після цілого року з тими самими дітьми. Вони вирішують, що найкращим поділом на три класи відповідно до цих умов буде такий, за якого жодна дитина не буде у класі з дитиною, яка не входить до перших позицій у її списку вподобань, причому вибирається якомога меншим. Зауважте, що склад нового класу може цілком збігатися з торішнім, але вже з новою вихователькою!
Перший рядок містить кількість дітей (n \le 200), яких потрібно перерозподілити у дитячому садку. Діти пронумеровані числами від до .
Наступні рядків описують дітей. -ий рядок містить номер поточного вихователя (ціле число , або ) та n - 1 ціле число \{1, 2, 3, \ldots, i-1, i+1, \ldots, n\} у деякому порядку, які задають список переваг для -ї дитини у спадному порядку.
Найменше невід'ємне ціле , для якого існує таке розбиття дітей на три нових групи, що
жодна дитина не має того ж вихователя, що і у старій групі
усі друзі по новій групі для кожної дитини знаходяться серед топ місць у списку переваг.
Приклад 1