Expansão rodoviária

Diz a lenda que, há muito tempo, o Serviço de Bandeirantes Conectados (SBC) administrava uma rede de estradas bidirecionais que ligava diversas cidades. Naquela época, o traçado era extremamente simples: entre quaisquer duas cidades existia exatamente um único caminho.

Com o crescimento da população e o aumento no transporte de mercadorias, o Instituto de Cidades Planejadas e Conectadas (ICPC) assumiu o controle e decidiu modernizar a rede. Para evitar o trânsito interno nas cidades intermediárias e agilizar as viagens, foram construídas novas estradas diretas entre certos pares de cidades. Uma nova estrada era criada entre duas cidades $A$ e $B$ sempre que, no traçado original, o caminho entre elas passava por exatamente uma única cidade intermediária.

Hoje, só conhecemos o mapa atual da rede, e o ICPC quer descobrir se ele pode mesmo ter surgido seguindo esse processo. Sua tarefa é analisar o mapa atual e determinar se a lenda pode ser verdadeira. Caso seja possível, também deve reconstruir e imprimir um possível traçado original da rede.

A primeira linha contém dois inteiros $N$ e $M$ $(3 ≤ N ≤ 10^5 , 2 ≤ M ≤ 4 × 10^5 )$, representando, respectivamente, o número de cidades e o número de estradas no mapa atual.

Cada uma das $M$ linhas seguintes contém dois inteiros $u_i$ e $v_i$ $(1 ≤ u_i , v_i ≤ N , u_i \ne v_i )$, indicando que há uma estrada bidirecional entre as cidades $u_i$ e $v_i$ . No mapa atual, é garantido que existe um caminho entre qualquer par de cidades e não há mais de uma estrada entre o mesmo par de cidades.

Caso o mapa atual possa ter surgido seguindo o processo descrito na lenda, a saída deve conter $N − 1$ linhas. Cada linha deve conter dois inteiros $a_i$ e $b_i$ $(1 ≤ a_i , b_i ≤ N , a_i \ne b_i )$, representando que havia uma estrada direta entre as cidades ai e bi no traçado original.

Caso contrário, a saída deve conter apenas uma linha com um único caractere “*” (asterisco). Caso haja mais de um possível traçado original, você pode imprimir qualquer um deles.