У єдиному рядку через пропуск записано числа x₁ y₁ x₂ y₂ … x_i y_i … – номери кінців даних хорд.

Перш за все необхідно визначити і записати у порядку зростання вершини многокутника, їх кількість – k дорівнює числу точок, що є кінцями даних хорд (на мал. 1.1 k = 6). Зауважимо, що точки, не сполучені відрізками, до уваги брати зовсім не слід, адже вони не використовуються у задачі. Саме тому k, яке в умові означає загальну кількість точок, на першому ж етапі розв’язування становитиме кількість задіяних точок. У даному прикладі k дорівнює c – числу проведених хорд. Сторонами даного многокутника є хорди, які не мають внутрішніх перетинів, а його діагоналями (мал. 1.2) є хорди, що перетинаються. Дані задачі можна ізоморфно відобразити на відрізок з координатами 1 - 6 (мал. 1.3), поєднавши допоміжними відрізками координати, відповідні номерам кінців даних хорд. Кількість даних діагоналей многокутника d дорівнює кількості пар допоміжних відрізків, які мають не пусті і не рівні одному з відрізків перерізи. Проте, можна без цього обійтись, якщо помітити, що ті з хорд, що є сторонами многокутника, на кінцях мають точки, різниця номерів яких дорівнює 1. Якщо позначити p – число проведених сторін многокутника, то d = c – p.

Число min – кількість не побудованих сторін многокутника (на мал. 1.2 зображені пунктиром) дорівнює k-(l – d), тобто min = k – p. Кількість не проведених діагоналей обчислюється за формулою n = k*(k - 3)/2 - d.
Основною робочою підпрограмою може бути логічна функція перевірки на перетин двох хорд. Кожну хорду зручно записати у записі
lin = record
            begln, endln: integer;
        end,
де begln та endln – координати початку та кінця хорд, а всі хорди – у масиві
lines: array[1..100] of lin.

У першому рядку через пропуск записані числа: m (1 ≤ m ≤ 20) - кількість маршрутів, n (2 ≤ n ≤ 100) - кількість зупинок, A та B – номери зупинок, для яких потрібно підрахувати кількість пересадок. Кожен із наступних m рядків складається з p_i чисел (2 ≤ p_i ≤ 100) – номерів зупинок на i-му маршруті.

У єдиний рядок записати число k - найменшу кількість потрібних пересадок або число -1, якщо це не можливо.

Зобразимо транспортну мережу у вигляді графа, де зупинками будуть пронумеровані вершини. На малюнку 2.1, який відображає другий приклад, є два маршрути із зупинками 1 – 10. Для наочності зупинки першого маршруту з’єднаємо суцільними стрілками, а зупинки другого маршруту - пунктирними стрілками. Всі зупинки першого маршруту, що містить зупинку А, тобто №3, помітимо числом 0. Зупинки другого маршруту, який має спільні з першим маршрутом зупинки 4 та 7, помітимо числом 1 (малюнок 2.2). Очевидно, до будь-якої зупинки, поміченої числом 1, в тому числі і до зупинки В (№8) від зупинки А можна дістатись з однією пересадкою. Подібним чином, всі зупинки, суміжні з маршрутом, зупинки якого помічені числом 1, помітимо числом 2 і. т.д. Залишиться визначити число, яким помічені зупинки маршруту, що містить зупинку В. Воно і буде шуканим числом k. Використаємо структуру даних множина (set). Нехай L[i] - множина зупинок, розміщених на i-му маршруті (тобто L - масив множин), cur - множина зупинок, до яких можна дістатись, здійснивши не більшее step пересадок. Побудуємо множину next зупинок, до яких можна дістатись, зробивши не більше (step+1) пересадок. По-перше, всі зупинки з множини cur входять до множини next. По-друге, якщо на якусь зупинку можна потрапити не більше ніж за step пересадок, і ця зупинка належить в тому числі й маршруту i, то тоді на будь-яку зупинку маршруту i можна потрапити за не більше ніж (step+1) пересадок. Тобто, якщо переріз множин cur та L[i] не пустий, всі елементи множини L[i] потрібно включити в множину next: next := next + L[i] (об’єднання множин). Залишилось помітити, що коли транспортна мережа міста складається з m маршрутів, то або із зупинки A на зупинку B можна потрапити не більш ніж з (m-1)-ю пересадкою, або не можна потрапити взагалі (A і B лежать в різних компонентах зв’язності графа). Таким чином, для розв’язання задачі Transp необхідно вміти оперувати типом “множина“ (set), до речі, знати елементарні відомості з алгебри логіки та перевіряти граф на зв’язність немає, адже перевірка на зв’язність графа G, який має множини вершин зв’язних підграфів U та V (G=U∪V), здійснюється шляхом перевірки умови U∩V≠∅.

Збережемо інформацію про маршрути в масиві множин ss. Тобто для кожного маршруту, номери зупинок, які належать цьому маршруту будуть розміщені у відповідній множині. У множину s будемо поміщати маршрути, які досяжні з початкової зупинки не більше ніж за k пересадок. Якщо мережа маршрутів буде не зв’язною, і з початкової зупинки до кінцевої, не зходячи з маршруту, добратися неможливо, то дана програма також зуміє це визначити: якщо на якомусь кроці ні одного нового маршруту до досяжним не добавиться, то кінцева зупинка не досяжна.

На перетині i-го рядка та j-го стопчика квадратної таблиці n x n записано число 1, якщо i-а і j-а людини є прямими родичами, і число 0, якщо для цих людей відсутній прямий родинний зв’язок.

В єдиному рядку записати число min, або слово "not", якщо це число знайти не можливо.

Дані зручно проілюструвати на графі (див. мал. 3.1). У наведеному прикладі маємо справу іх зв’язним графом. Але, як видно з малюнка, відповідно умові, він двохдольний, тобто множина всіх вершин G=U∪V, де множини U=(1,2,3,4) та V=(5,6,7,8,9), причому U∩V=∅.

Всі вершини множини U будуть позначені парними числами, а вершини множини V – непарними.

У першому рядку записано через пропуск числа m та n – довжина і ширина лісу (m, n ≤ 50), у наступних i (i ≤ m*n) рядках по два числа x_i та y_i – координати обстежених квадратів.

З малюнку 4, де зображено ліс із розмірами та розміщенням обстежених квадратів (заштриховані) відповідно наведеному прикладу, видно, що ізольованих не обстежених ділянок три (вони пронумеровані). Для розв’язування задачі зручно використати структуру “черга”. Спочатку в чергу слід занести будь-який ще не обстежений квадрат. Потім, доки черга не стане пустою, слід видаляти з неї перший квадрат і додавати в чергу всі суміжні з поточним необстежені квадрати. Черга обнулиться, коли закінчиться перша не обстежена ділянка. Далі, доки не закінчаться всі ще не обстежені квадрати, слід шукати новий не обстежений квадрат і повторювати вже щойно описане. Програма може вийти досить громіздкою, тому бажано виділити в окремі підпрограми ВВОД даних, ВИЗНАЧЕННЯ НАЯВНОСТІ НЕ ОБСТЕЖЕНИХ КВАДРАТІВ, ДОДАВАННЯ В ЧЕРГУ та ВИЛУЧЕННЯ З ЧЕРГИ.

Це класична задача на пошук в глибину графа. Зрозуміло, що треба обходити матрицю і якимось чином обчислювати кількість ізольованих не обстежених ділянок. Варіант вирішення такий: після того, як ми потрапляємо на ділянку, треба це зафіксувати збільшивши змінну-результат на одиницю. Щоб вдруге не порахувати одну і туй ж ділянку, відразу після відвідин необхідно її знищити, тобто присвоїти всім клітинам ділянки значення нуль. Оскільки тест завдання не надто малий, варто написати процедуру знищення ділянок, назвемо її "count". Щоб під час виконання процедуру не «вискочити" за межі масиву, зробимо його не розміром m x n, а розмірів m+2 x n+2, це дасть нам можливість оточити шуканий масив розміром m x n нулями.