Há no fundo do horizonte um jardim muito remoto que é conhecido pela quantidade enorme de plantas. Há exatamente N plantas, numeradas de 1 a N, sendo que cada uma está plantada num canteiro próprio. Os diferentes canteiros estão ligados por M trilhos. Cada trilho une dois canteiros distintos e há no máximo um trilho entre dois canteiros. É possível ir de um canteiro até qualquer outro seguindo os trilhos.
Pretende-se dividir os canteiros em dois grupos que obedecem a uma restrição particular: se dois canteiros estão no mesmo grupo, então não existe nenhum trilho entre eles (nota que podem existir trilhos entre canteiros de grupos diferentes). Infelizmente nem sempre é possível fazer esta divisão, a tua tarefa é determinar se é possível ou não.
Se N = 4, M = 4 e tivermos os seguintes trilhos: (1, 2) (ou seja, há um trilho entre o canteiro 1 e 2), (2, 3), (3, 4), (4, 1), podemos agrupar os canteiros 1 e 3 num grupo e os canteiros 2 e 4 noutro, logo a resposta para este caso de teste é "sim".
A seguinte figura ilustra este caso:
Se N = 4, M = 4 e tivermos os seguintes trilhos: (1, 2), (1, 4), (2, 3), (2, 4), não há forma válida de agrupar estes canteiros, logo a resposta é "não".
A seguinte figura ilustra este caso:
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ N ≤ 104 | Número de canteiros | |
| N - 1 ≤ M ≤ 5 · 104 | Número de trilhos |
Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 10 | 1 ≤ N ≤ 10, 1 ≤ M ≤ 45 |
| 2 | 30 |
Uma floresta de canteiros é um conjunto de canteiros que obedece à seguinte propriedade: entre dois canteiros do conjunto existe no máximo um caminho usando apenas trilhos entre canteiros do conjunto (uma maneira mais formal de dizer isto é que subgrafo induzido pelos canteiros do conjunto é acíclico). Pretendemos encontrar uma floresta com pelo menos K canteiros.
Um conjunto de ciclos de canteiros é um conjunto de conjuntos ordenados de canteiros, onde os conjuntos ordenados de canteiros obedecem à seguinte propriedade: existe um trilho entre cada canteiro consecutivo do conjunto assim como um trilho entre o primeiro e o último canteiros (uma maneira mais formal de dizer isto é que formam um ciclo não necessariamente induzido). Adicionalmente, cada canteiro pode aparecer no máximo num dos conjuntos. Pretendemos encontrar um conjunto de ciclos de canteiros com pelo menos N - K canteiros usados (ou seja, a soma do número de canteiros em cada conjunto ordenado é pelo menos este valor).
Nem sempre é possível encontrar um destes por isso só é necessário encontrar um dos dois, isto é, a tua tarefa é encontrar uma floresta de canteiros com pelo menos K canteiros OU um conjunto de ciclos de canteiros com pelo menos N - K canteiros (mesmo que encontres dois, só deves reportar um).
Suponhamos que N = 5, M = 6 e tivermos os seguintes trilhos: (1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5).
A seguinte figura ilustra este caso:
Se K = 3 podemos escolher a seguinte floresta de canteiros com 3 canteiros: 3, 4, 5.
Se K = 4 podemos escolher o conjunto de ciclos que contém apenas um ciclo de comprimento 3 usando os canteiros: 2, 3, 4 (por esta ordem).
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ N ≤ 104 | Número de canteiros | |
| N - 1 ≤ M ≤ 5 · 104 | Número de trilhos | |
| 1 ≤ K ≤ N - 1 | Valor objetivo |
Os casos de teste desta parte do problema estão organizados em 3 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 3 | 10 | 1 ≤ N ≤ 1 000, 1 ≤ M ≤ 5 000, K ≥ N - 2 |
| 4 | 20 | 1 ≤ N ≤ 1 000, 1 ≤ M ≤ 5 000 |
| 5 | 30 |
Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Parte | Restrições adicionais |
|---|---|---|---|
| 1 | 10 | Parte I | 1 ≤ N ≤ 10, 1 ≤ M ≤ 45 |
| 2 | 30 | Parte I | |
| 3 | 10 | Parte II | 1 ≤ N ≤ 1 000, 1 ≤ M ≤ 5 000, K ≥ N - 2 |
| 4 | 20 | Parte II | 1 ≤ N ≤ 1 000, 1 ≤ M ≤ 5 000 |
| 5 | 30 | Parte II |
Nota: O formato de input é difere entre as duas partes.
Nota 2: Este problema é multiteste, o que significa que o vosso programa deve ler e resolver vários casos de teste de uma vez.
A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.
Segue-se uma linha com um inteiro, T que representa o número de casos de teste. T será no máximo 15. Seguem-se T blocos de linhas com o seguinte formato cada:
Para a Parte I, vem primeiro uma linha com dois inteiros separados por espaços, primeiro N, representando o número de canteiros, seguido de M, o número de trilhos. Na Parte II esta linha tem três inteiros separados por espaços, N, M e K, o valor objetivo.
Seguem-se M linhas, cada uma contendo dois inteiros separados por espaços, os índices dos dois canteiros que este trilho une.
É garantido que o conjunto de trilhos é conexo, não há trilhos repetidos e não há trilhos de um canteiro para ele próprio.
O output deve conter uma linha por cada caso de teste com a palavra "sim", caso a divisão seja possível, ou "nao" (sem acento), caso não seja.
Para cada caso de teste, o output deve começar com uma frase, ou "floresta", caso queiram reportar uma floresta de canteiros, ou "ciclos", caso queiram reportar um conjunto de ciclos.
Se a vossa resposta for inválida, por exemplo, a floresta que indicam não é uma floresta, um ciclo não é um ciclo válido, o tamanho da floresta ou do conjunto de ciclos é pequeno de mais, então o resultado do vosso programa será Resposta Errada.
1 2 4 4 1 2 2 3 3 4 4 1 4 4 1 2 2 3 3 4 4 2
sim nao
Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.
2 2 5 6 3 1 2 1 3 2 3 2 4 3 4 4 5 5 6 4 1 2 1 3 2 3 2 4 3 4 4 5
floresta 3 3 4 5 ciclos 1 3 2 3 4
Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.