Корпорация RoboCorp2021 занимается производством изделий с использованием роботов. Каждый из роботов имеет ряд возможностей по обработке деталей, и каждый из роботов может передать обработанную им деталь некоторым другим роботам. Роботы пронумерованы от 1 до N. Руководство RoboCorp2021 решило оптимизировать производство и улучшить роботов. Заметив, что самой долгой и затратной оказалась операция передачи деталей от одного работа другому роботу, руководство решило, чтобы одна и та же деталь по возможности не обрабатывалась разными роботами. Однако оказалось, что совместить все возможные обработки в одном роботе не всегда возможно и окупаемо. Было подсчитано, что заменять двух роботов на одного нужно только тогда, когда переданная деталь от первого робота второму может быть возвращена обратно первому роботу. При этом передача детали может быть сделана как сразу от первого второму, так и через несколько других роботов. Аналогично рассматривается и передача в обратную сторону.

Зная количество роботов на устаревшем производстве, и кому они могли передавать детали, посчитайте, сколько будет использоваться роботов в новом производстве. Учтите, что если первый робот может передать деталь второму роботу, но эта деталь уже не может вернуться к первому, то нужны будут оба робота.

Описание устаревшего производства имеет следующий вид. На первой строке находится целое число N – количество роботов.

На следующих N строках: первое целое число K – это количество тех роботов, которым может быть передана деталь от i-го робота, где i – номер строки и номер соответствующего робота, далее K целых чисел Mj – номера этих роботов. 1 ≤ Mj ≤ N.

Например, для входных данных

7
3 2 3 4
1 1
1 2
0
0
1 7
1 6

количество роботов, которое будет использоваться в новом производстве будет равно 4.

В поле для ввода ответа запишите одно целое число – количество роботов, которое будет использоваться в новом производстве, для входных данных

15
2 2 3
0
0
0
4 6 7 8 9
0
0
0
0
0
1 12
0
0
0
0

A=5

Объяснение:

74 mod A = 4

Остаток меньше делителя, поэтому A>=5

Подставляем 5 в основание системы счисления и проверяем результат.

74/5=14 остаток   4

14/5=2 остаток   4

2/5=0 остаток   2

Десятичное число 27 в пятиричной системе счисления записывается как 244. Следовательно A=5

Как решать подобные задачи.

1.

Согласно правилу перевода десятичного числа M в A-ричную систему, в последний разряд A-ричного числа записывается остаток от M/A. То есть M mod A = R, где R – значение последнего разряда A-ричного числа. Вспоминаем что остаток всегда меньше делителя, поэтому A>=R+1. В рассматриваемой задаче A>=5.

Определение нижней границы значения A, позволяет сузить поиск. В рассматриваемой задаче мы с первого раза вышли на верное значение, но так бывает не всегда.

2.

Представим число M в следующем виде: M=A*B+R, где A - основание системы счисления, а R – остаток. В рассматриваемой задаче эта запись приобретает следующий вид: 74=A*B+4 или 70=A*B. То есть необходимо найти такие целые числа, чтобы их произведение равнялось 70.

Рассмотрим варианты A*B.

1*70

2*35

5*14

7*10

В первом пункте мы выяснили, что A>=5, поэтому первые два варианта отпадают. Остаются варианты 5*14 и 7*10.

Проверив истинность высказываний 74 mod 5 = 4 и 74 mod 7 = 4, убеждаемся, что A=5.

3.

Зная разрядность, также можно производить вычисления.

Обозначим разрядность через N.

N= [L]+1 , где L – значение логарифма от M по основанию A. Квадратные скобки – обозначают целое значение.

В рассматриваемой задаче, число M в A-ричной системе счисления трехзначное. То есть N=3.

3=[L]+1

[L]=2

Для проверки разрядности значения A*B в системе счисления A, следует проверить истинность выражения N= [L]+1.

В рассматриваемой задаче, это условие соблюдается только когда A принимает значения 5, 6, 7 или 8. Только при таких значениях A, число M в A-ричной системе счисления A будет трехзначным.  

Числа 6 и 8 не подходят, поскольку второй множитель B также должен быть целочисленным.

Остаются числа 5 и 7.

Проведя проверку на остаток от деления 74 mod 5 = 4 и 74 mod 7 = 4, получаем искомое значение A=5.

A=5

Объяснение:

74 mod A = 4

Остаток меньше делителя, поэтому A>=5

Подставляем 5 в основание системы счисления и проверяем результат.

74/5=14 остаток   4

14/5=2 остаток   4

2/5=0 остаток   2

Десятичное число 27 в пятиричной системе счисления записывается как 244. Следовательно A=5

Как решать подобные задачи.

1.

Согласно правилу перевода десятичного числа M в A-ричную систему, в последний разряд A-ричного числа записывается остаток от M/A. То есть M mod A = R, где R – значение последнего разряда A-ричного числа. Вспоминаем что остаток всегда меньше делителя, поэтому A>=R+1. В рассматриваемой задаче A>=5.

Определение нижней границы значения A, позволяет сузить поиск. В рассматриваемой задаче мы с первого раза вышли на верное значение, но так бывает не всегда.

2.

Представим число M в следующем виде: M=A*B+R, где A - основание системы счисления, а R – остаток. В рассматриваемой задаче эта запись приобретает следующий вид: 74=A*B+4 или 70=A*B. То есть необходимо найти такие целые числа, чтобы их произведение равнялось 70.

Рассмотрим варианты A*B.

1*70

2*35

5*14

7*10

В первом пункте мы выяснили, что A>=5, поэтому первые два варианта отпадают. Остаются варианты 5*14 и 7*10.

Проверив истинность высказываний 74 mod 5 = 4 и 74 mod 7 = 4, убеждаемся, что A=5.

3.

Зная разрядность, также можно производить вычисления.

Обозначим разрядность через N.

N= [L]+1 , где L – значение логарифма от M по основанию A. Квадратные скобки – обозначают целое значение.

В рассматриваемой задаче, число M в A-ричной системе счисления трехзначное. То есть N=3.

3=[L]+1

[L]=2

Для проверки разрядности значения A*B в системе счисления A, следует проверить истинность выражения N= [L]+1.

В рассматриваемой задаче, это условие соблюдается только когда A принимает значения 5, 6, 7 или 8. Только при таких значениях A, число M в A-ричной системе счисления A будет трехзначным.  

Числа 6 и 8 не подходят, поскольку второй множитель B также должен быть целочисленным.

Остаются числа 5 и 7.

Проведя проверку на остаток от деления 74 mod 5 = 4 и 74 mod 7 = 4, получаем искомое значение A=5.