Por OBI - Olimpíada Brasileira de Informática 2010 Brazil
A OBI (Organização Brasileira dos Índios) promoverá um festival indígena, onde várias tribos irão se reunir e fazer demonstrações de cultura, como artesanato, danças, pinturas, comidas e etc.
Uma das tribos é a dos Tunak Tunak, que possuem uma apresentação de dança muito peculiar. Nessa dança, existem N toras de madeira encrustadas no chão, dispostas de maneira circular e igualmente espaçadas. Em algumas dessas toras fica um índio, olhando em sentido horário ou anti-horário.
A cada batida do tambor, os índios pulam para a próxima tora (que depende da direção para onde ele está olhando no momento). Durante a dança, porém, algumas coisas podem acontecer:
Note que se o índio não pula e inverte seu sentido, mas ao mesmo tempo um outro índio cair na mesma tora no sentido contrário, caimos no primeiro caso, e ambos os índios na tora invertem seus sentidos (assim, o índio que estava na tora anteriormente inverte seu sentido novamente).
A dança termina quando as toras ocupadas por um índio são exatamente as mesmas toras ocupadas no início da dança, não importando qual índio está em cada tora e nem os sentidos para onde eles estão pulando.
A figura abaixo ilustra (a) uma configuração inicial com oito toras e seis índios; (b) a posição dos índios após uma batida de tambor; e (c) a posição dos índios após duas batidas de tambor.
Os índios querem se preparar para a dança e precisam saber quanto tempo ela vai durar.
Para isso, você deverá escrever um programa que, dados a quantidade de toras que serão utilizadas, a quantidade de índios e a posição inicial de cada um, calcule quantas batidas de tambor levará para que a dança termine.
A primeira linha da entrada possui 2 inteiros: N (3 ≤ N ≤ 1.000.000) e E (1 ≤ E ≤ 1000), que são, respectivamente, a quantidade de toras e a quantidade de índios que irão dançar (E ≤ N). As próximas E linhas contém, cada uma, a descrição da posição inicial de cada índio. Cada linha possui dois inteiros: V (1 ≤ V ≤ N) e D (D = 1 ou D = -1) que representam, respectivamente, o número da tora onde o índio inicia e seu sentido inicial (1 se horário, -1 se anti-horário). A numeração das toras obedece o sentido horário. No início da dança uma tora terá, no máximo, um índio.
Seu programa deverá exibir um número inteiro representando a quantidade de batidas de tambor necessárias para que a dança acabe.
Exemplos de Entrada | Exemplos de Saída |
6 4 2 1 3 1 5 1 6 1 |
3 |
3 1 2 -1 |
3 |
8 6 2 -1 3 1 4 -1 6 1 7 -1 8 1 |
4 |