ICPC

For many years, there has been a mysterious cult known as ICPC. Eyewitnesses report that its followers engage in strange rituals. They form groups of $3$ and worship a screen that emits a mysterious glow, fervently pressing buttons grouped on an enigmatic panel. The interaction is not entirely one-sided; sometimes the "deity" responds with signs of approval, and the followers cheer with joy. However, for most inattentive followers, this happens rarely. More often, the "deity" is displeased, leaving the followers first confused, and then saddened.

There are various rumors about the nature of the "deity." Some claim it exists in many forms, each controlled by a designated person (or perhaps not a person at all, but a being of higher order) — the Admin. The so-called Admin with the Great Beard is particularly famous. There have long been rumors about the deity's special fondness for kefir... But that's just nonsense, and we've strayed from the topic.

Now, to the heart of the matter. Once, $N$ followers of the ICPC cult gathered and decided that the traditional methods of worship were outdated, boring, and not particularly sinister. They decided to transfer dark energy instead of smashing away at the keyboard. A plan was created — a set of $M$ pairs $(A,B)$, meaning that follower $A$ must transmit energy to follower $B$ (and so, follower $B$ must receive energy from $A$).

They started following the plan, but the energy did not transfer. Clearly, the problem couldn't possibly be the lack of dark energy among the ICPC followers! The followers realized this, and after a while, they understood that for the plan to succeed, they needed a specific arrangement. They drew a magic circle and positioned themselves around its perimeter.

But a mere circle is not enough; the energy transfer process needs to be associated with the circle. It is known that energy transfer is associated with a circle if every follower transfers energy directly to the followers immediately next along the circle (when traversing the circle clockwise) and receives energy from the followers immediately preceding them in the circle.

Let's state this formally. Let $\text{next}(X)$ be the number of the follower directly after $X$ in the circle (when traversing the circle clockwise), and $\text{prev}(X)$ be the number directly before $X$ in the circle. For i > 1, let \textbf{next}^i(X) = \textbf{next}(\textbf{next}^{i-1}(X)) and \textbf{prev}^i(X) = \textbf{prev}(\textbf{prev}^{i-1}(X)) (and assume \textbf{next}^1(X) = \textbf{next}(X) and \textbf{prev}^1(X) = \textbf{prev}(X)). Energy transfer is associated with the magic circle if for each follower the following conditions hold:

• They transfer energy to followers \textbf{next}^i(X), 1 \leq i \leq A, where $A$ is the total number of followers they transfer energy to;

• They receive energy from followers \textbf{prev}^i(X), 1 \leq i \leq B, where $B$ is the total number of followers they receive energy from.

The goal was never so close, but the ICPC followers could not arrange themselves to achieve energy transfer associated with the magic circle. As fellow members of the ICPC cult, you will certainly do your best to help them!