XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: musica.x, onde x deve ser c, cpp, java, js ou py

Música para Todos

Uma empresa de streaming de músicas lançou uma nova funcionalidade, para grupos de amigos ouvirem em seus aparelhos a mesma música ao mesmo tempo, compartilhando assim um momento de alegria nestes tempos difíceis de pandemia.

Cada amigo no grupo tem que declarar uma música que adora e uma música que detesta. Um amigo fica satisfeito se a música que está sendo compartilhada não é a música que ele detesta. Se a música que está sendo compartilhada é detestada por um dos amigos, ele pode trocar a música sendo compartilhada pela música que ele adora. Se há mais de um amigo que detesta a música que está sendo compartilhada, somente o amigo que é cliente há mais tempo da empresa é que pode trocar a música (e troca pela música que adora).

Obviamente, após a troca da música compartilhada pode ser que outro amigo deteste a nova música, e uma nova troca pode ocorrer. E as trocas podem ser intermináveis!

Dadas as preferências de um grupo de amigos e a música sendo compartilhada, e considerando que sempre ocorre troca enquanto houver amigo não satisfeito, escreva um programa para determinar quantas trocas ocorrem até que todos os amigos estejam satisfeitos.

Entrada

A primeira linha da entrada contém três inteiros N, M e C, respectivamente o número de amigos, o número de músicas e a música que está sendo compartilhada. As músicas são identificadas por inteiros de 1 a M. Cada uma das N linhas seguintes descreve as escolhas de um amigo e contém dois inteiros A e D, identificando respetivamente a música adorada e a música detestada. A ordem dos amigos na entrada obedece à ordem em que os amigos se tornaram clientes da empresa (o amigo que aparece antes é cliente há mais tempo).

Saída

Seu programa deve produzir uma única linha na saída, contendo um único inteiro, o número de trocas até que todos os amigos fiquem satisfeitos ou o número -1 se as trocas continuam indefinidamente.

Restrições

  • 1 ≤ N ≤ 105
  • 1 ≤ M ≤ 105
  • 1 ≤ C ≤ M
  • 1 ≤ A,D ≤ M e A &neq; D

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 40 pontos, 1 ≤ N,M ≤ 1000.

Exemplos

Entrada
3 4 2
1 2
2 3
3 2
Saída
1
	

 

Entrada
4 5 2
1 3
2 3
3 2
5 1
Saída
3
	

 

Entrada
3 3 1
1 2
2 3
3 1
Saída
-1
	

 

Promoção
logo sbc
Patrocínio
Apoio
Coordenação