섬

생쥐 Squeaky는 사람이 사는 원형 섬을 발견하고, 이 새로운 발견을 알리기 위해 고향으로 항해하고 있다. 섬은 원형이고 대부분이 암석으로 이루어진 농경 불가능한 땅이다. 그래서 짠물고기가 주민들의 주된 식량원이며, 주민들은 섬 해안을 따라 N개의 마을(1번부터 N번까지)에 살고 있다.

마을을 연결하기 위해 섬 내부에 M개의 교차점을 만들고, 마을과 교차점을 잇는 도로를 몇 개 건설했다. 건설 비용을 최소화하기 위해 정확히 N + M − 1개의 도로를 건설하여, 어떤 두 마을 사이든 도로로 이동할 수 있고 각 마을에 끝나는 도로가 정확히 하나가 되도록 했다. 다시 말해, 도로망은 N개의 잎(N개의 마을), M개의 내부 노드(M개의 교차점), N + M − 1개의 간선(N + M − 1개의 도로)을 가진 트리로 나타낼 수 있다.

또한 모든 교차점에는 적어도 세 개의 도로가 연결되어 있고, 도로는 교차점이 아닌 곳에서 다른 도로와 만나지 않으며, 다리나 터널은 없다(비용이 많이 든다).

다음은 마을 37개, 교차점 20개, 도로 56개로 이루어진 섬 지도의 예시이다.

그림 1: 섬 지도의 예시

이 섬이 너무 흥미로워서 Squeaky는 더 큰 배를 타고 섬 전체를 항해하며 해안을 따라 위치한 순서대로 마을을 방문하는 다음 여행을 이미 계획하고 있다. 그러려면 해안을 따라 마을이 놓인 순서를 아는 것이 중요하다.

안타깝게도 귀향 중 강한 바람 때문에 Squeaky가 정성껏 만든 지도가 배에서 날아가 바다 깊은 곳으로 영원히 사라졌다.

하지만 모든 것을 잃은 것은 아니다. Squeaky는 섬의 모든 도로의 두 끝점을 적어 둔 작은 일지를 가지고 있었다. 이 정보로부터 원형 해안을 따라 가능한 마을 순서를 찾으려 하며, 당신에게 그것을 찾아 달라고 부탁했다. 섬이 원형이므로 같은 순서의 회전은 동등하게 취급된다(자세한 내용은 예시 참고).

과제를 완수하려면 해안을 따라 가능한 마을 순서의 수 P를 알아야 한다. 이 수는 클 수 있으므로, 이 값을 양의 지수를 가진 인수들의 곱으로 나타내어라(자세한 내용은 출력 부분 참고).

프로그램은 표준 입력에서 읽어야 한다.

입력의 첫 줄에는 두 양의 정수 N과 M이 주어지며, N은 마을의 수, M은 교차점의 수이다.

다음 N + M − 1개의 줄에는 각각 두 정수 u와 v가 주어진다. 이는 번호 u인 마을 또는 교차점이 번호 v인 마을 또는 교차점과 직접 도로로 연결되어 있음을 뜻한다. (u ≤ N이면 마을이고, 그렇지 않으면 교차점이다. v도 마찬가지이다.)

입력은 위에 명시된 모든 조건을 만족하며, 입력을 만족하는 유효한 도로망이 적어도 하나 존재함이 보장된다.

프로그램은 표준 출력에 써야 한다.

프로그램은 해안을 따라 가능한 마을 순서의 수 (P)를 설명하는 (K)개의 줄을 출력해야 한다.

(i)번째 줄에는 정확히 두 정수 (a_i)와 (b_i)가 있어야 한다.

출력은 다음을 만족해야 한다.

• (P = a^{b_1}_1a^{b_2}_2a^{b_3}_3\cdots a^{b_K}K) (또는 동등하게, (P = \prod{i=1}^{K}{a^{b_i}_i}))
• (1 \le a_i, b_i \le 10^{18})
• (0 \le K \le 10^6)

가능한 순서의 수가 이 형태로 표현될 수 있음이 보장된다.

• N ≥ 2
• M ≥ 0
• N + M ≤ 200 000