ICPC

Протягом багатьох років існує таємничий культ під назвою ICPC. За свідченнями очевидців, його послідовники виконують дивні ритуали. Вони утворюють групи по $3$ особи та поклоняються екрану, який випромінює загадкове світіння, гаряче натискаючи кнопки на незрозумілій панелі. Взаємодія не є цілком односторонньою: іноді "божество" відповідає знаками схвалення, і тоді послідовники радіють. Однак для більшості неуважних послідовників це трапляється рідко. Здебільшого ж "божество" незадоволене, а послідовники спочатку розгублені, а потім засмучені.

Існують різні чутки щодо природи "божества". Дехто стверджує, що воно існує у багатьох формах, кожною з яких керує призначена особа (а може й не особа зовсім, а істота вищого порядку) — Адмін. Особливо відомий так званий Адмін з Великою Бородою. Давненько вже ходять чутки про особливу любов божества до кефіру… Але це нісенітниця, і ми відволіклися від теми.

Переходимо до суті. Якось $N$ послідовників культу ICPC зібралися разом і вирішили, що традиційні способи поклоніння вже застарілі, нудні й не надто зловісні. Вони вирішили замість натискання клавіш передавати темну енергію. Був розроблений план — набір з $M$ пар $(A,B)$, що означає, що послідовник $A$ повинен передати енергію послідовнику $B$ (відповідно, $B$ має прийняти енергію від $A$).

Вони почали діяти згідно з планом, проте енергія не передавалася. Очевидно, проблема аж ніяк не могла полягати в нестачі темної енергії серед послідовників ICPC! Послідовники це зрозуміли, і з часом збагнули, що для успіху плану їм потрібно влаштуватися певним чином. Вони накреслили магічне коло і розташувалися по його колу.

Але простого кола недостатньо; процес передачі енергії повинен бути пов'язаний з колом. Відомо, що передача енергії пов'язана з колом, якщо кожен послідовник передає енергію безпосередньо тим, хто знаходиться відразу після нього по колу (за обходом кола за годинниковою стрілкою), і приймає енергію від тих, хто стоїть відразу перед ним.

Сформулюємо це формально. Нехай $\text{next}(X)$ — номер послідовника, який стоїть безпосередньо після $X$ по колу (за обходом за годинниковою стрілкою), а $\text{prev}(X)$ — номер безпосередньо перед $X$ по колу. Для i > 1 введемо \textbf{next}^i(X) = \textbf{next}(\textbf{next}^{i-1}(X)) і \textbf{prev}^i(X) = \textbf{prev}(\textbf{prev}^{i-1}(X)) (і вважатимемо \textbf{next}^1(X) = \textbf{next}(X), \textbf{prev}^1(X) = \textbf{prev}(X)). Передача енергії пов'язана з магічним колом, якщо для кожного послідовника виконуються умови:

• Він передає енергію послідовникам \textbf{next}^i(X), 1 \leq i \leq A, де $A$ — загальна кількість послідовників, яким він передає енергію;

• Він приймає енергію від послідовників \textbf{prev}^i(X), 1 \leq i \leq B, де $B$ — загальна кількість послідовників, від яких він приймає енергію.

Мета була вже так близько, але послідовники ICPC не змогли розташуватися так, щоб досягти передачі енергії, пов'язаної з магічним колом. Як співпослідовник культу ICPC, ти, звісно, зробиш усе можливе, щоб їм допомогти!