Problema H: Atenção à Tensão


image mesa_circular

Quem se lembra do Sr.  Delicado ? Ele ofereceu-se prontamente para nos próximos dias mediar uma série de reuniões de negócios entre os representantes de várias potências do mundo empresarial.

Para cada reunião serão convidados os representantes de N empresas (sendo N um número par). O Sr.  Delicado disponibilizou, no seu château, uma sala com N cadeiras dispostas à volta de uma mesa circular, igualmente espaçadas e numeradas de 1 a N no sentido dos ponteiros do relógio. Em cada cadeira ficará sentado o representante de uma empresa.

Como é natural, há rivalidades entre algumas das empresas, seja por parcerias passadas que não funcionaram da melhor forma, seja por inveja pelo sucesso da concorrência. O Sr.  Delicado foi previamente informado se, para cada par de empresas, existe algum tipo de rivalidade entre elas.

Cabe, enfim, ao anfitrião decidir o lugar onde se sentará o representante de cada empresa. É do seu interesse que se conste publicamente que as reuniões no seu château decorrem livres de discussões acaloradas e, por isso, quer evitar sentar quaisquer dois rivais frente a frente. Será possível fazê-lo?

Tarefa

Escreva um programa que, tendo em conta as rivalidades que se verificam entre algumas empresas, ajude o Sr.  Delicado a descobrir de quantas formas é possível sentar os representantes sem que haja dois rivais frente a frente.

Input

A primeira linha do input contém um inteiro, R, que corresponde ao número de reuniões que terão lugar no château do Sr.  Delicado durante os próximos dias. Para cada reunião, é fornecida a seguinte informação:
  • A primeira linha relativa a uma reunião contém dois inteiros, N e M, respetivamente o número de representantes das empresas que se irão reunir e o número de pares de empresas rivais.
  • A segunda linha contém N palavras, separadas por um espaço, indicando os nomes dos representantes das empresas. Cada nome é formado por (de 1 a 20) letras maiúsculas ou minúsculas, sem acentos nem cedilhas. Todos os nomes são diferentes.
  • Seguem-se M linhas, cada uma com dois nomes, A e B, separados por um espaço. Tal significa que a empresa cujo representante é A é rival da empresa cujo representante é B. É garantido que ambos os nomes correspondem a dois representantes diferentes e que cada par de rivais não aparece no input mais do que uma vez.

Restrições

  1  ≤  R  ≤  5 Número de reuniões
  2  ≤  N  ≤  12 e N é par Número de empresas convidadas para uma reunião
  0  ≤  M  ≤  N(N-1)/2 Número de pares de empresas rivais numa reunião

Output

O output tem uma linha por cada reunião, pela ordem definida no input. Se, para a respetiva reunião, existir alguma disposição dos representantes das empresas na qual não fiquem dois rivais sentados frente a frente, a linha tem a forma "Possivel: q" (sem aspas nem acento), onde q é o número de formas distintas de sentar os representantes sem que haja dois rivais frente a frente. No caso contrário, a linha tem a palavra "Impossivel" (sem aspas nem acento).

Exemplo

Input 

4
4 3
Amadeu Beatriz Carlos Daniel
Amadeu Carlos
Beatriz Carlos
Daniel Beatriz
4 4
Amadeu Beatriz Carlos Daniel
Amadeu Beatriz
Amadeu Carlos
Beatriz Carlos
Daniel Beatriz
4 0
Rita Tiago Manuel Susana
2 1
Paulo Raquel
Paulo Raquel

Output 

Possivel: 8
Impossivel
Possivel: 24
Impossivel

Nota

Dois exemplos de disposições válidas para a primeira reunião, onde o i-ésimo nome corresponde ao representante sentado na i-ésima cadeira (1  ≤  i  ≤  N), são:
  • Amadeu, Carlos, Beatriz, Daniel
  • Daniel, Amadeu, Carlos, Beatriz.


ToPAS'2022
193.136.122.94