Trilhas cromáticas
Uma rede tem estações e ligações não direcionadas. Cada ligação tem uma cor e recebe um número de a . Ligações diferentes podem conectar o mesmo par de estações, mas nenhuma liga uma estação a ela mesma.
Você deve dividir todas as ligações em percursos. Cada percurso usa pelo menos uma ligação, pode visitar uma estação várias vezes e não pode usar duas ligações consecutivas da mesma cor. Cada ligação da rede deve aparecer em exatamente um dos percursos, exatamente uma vez.
Os percursos podem começar e terminar em quaisquer estações, inclusive na mesma estação. Mesmo nesse caso, a primeira e a última ligação não são consideradas consecutivas: a regra compara apenas ligações em posições consecutivas na lista do percurso.
Encontre a menor quantidade de percursos e apresente uma divisão que atinja essa quantidade.
Input
A primeira linha contém e (, ).
Output
Imprima a quantidade mínima de percursos . Depois, imprima linhas, uma para cada percurso.
Cada linha deve conter , e os números de ligações: o tamanho do percurso, sua estação inicial e as ligações na ordem em que são percorridas. Partindo de , cada ligação deve ser percorrida a partir da estação atual. Qualquer divisão ótima será aceita.
Samples
Sample 1
Input
4 3 1 2 5 1 3 5 1 4 8
Output
2 1 1 1 2 4 3 2
O primeiro percurso vai de a , passando por , com cores e . O outro usa a ligação restante. Um único percurso não pode cobrir as três ligações.
Sample 2
Input
3 3 1 2 7 2 3 8 3 1 7
Output
1 3 1 1 2 3
As cores são . O percurso é válido: embora termine na estação inicial, não comparamos sua última ligação com a primeira.