시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Squeaky the Mouse has just discovered an inhabited, circular island and is sailing back to his homeland to announce this new discovery. The island is circular and made up mostly of rocky, non-arable land. As such, saltwater fish is the main food source to the inhabitants, so they reside in N towns (numbered 1 to N) along the coast of the island.

To connect the towns, M junctions have been created on the interior of the island and some roads built to connect the towns and the junctions. To minimise construction cost, exactly N + M − 1 roads are built such that it is possible to travel by road between any two towns, and there is exactly one road ending at each town. In other words, the road network may be represented as a tree with N leaves (representing the N towns), M internal nodes (representing the M junctions), and N + M − 1 edges (representing the N + M − 1 roads).

Furthermore, every junction has at least three roads connected to it, roads do not meet other roads except at junctions, and there are no bridges or tunnels (they are expensive).

Here is an example map of the island, with 37 towns, 20 junctions, and 56 roads:

Figure 1: Example map of the island

This island is so intriguing that Squeaky is already making plans for his next trip, in a bigger vessel, where he will sail around the whole island, visiting the towns in the order that they are located along the coast. To do this, it is important to know the ordering of the towns along the coast.

Unfortunately, due to strong winds during the journey home, the maps that Squeaky had meticulously crafted were blown off his ship and are now forever lost to the depths of the ocean.

However, not all is lost. Squeaky had brought along a small journal in which he noted down the two endpoints of every road on the island. From this information, he hopes to find the possible orderings of towns along the circular coast, and has tasked you to find them for him. Note that since this island is circular, rotations of the same ordering are treated as equivalent (see example for more details).

To complete your task, you need to know the number of possible orderings, P, of towns around the coast. Since this number may be large, write this value as a product of factors raised to positive exponents (see output section for details).

입력

Your program must read from standard input.

The first line of input contains two positive integers N and M, where N is the number of towns and M is the number of junctions.

The next N + M − 1 lines of input will each contain two integers u and v. This means that the town or junction numbered u has a direct road to the town or junction numbered v. (If u ≤ N, it represents a town; otherwise, it is a junction. Similarly for v.)

The input is guaranteed to fulfill all constraints stated above, and at least one valid road network is guaranteed to satisfy the input.

출력

Your program must write to standard output.

Your program must output \(K\) lines describing the number of possible orderings, \(P\), of towns around the coast.

The \(i\)th line must contain exactly two integers, \(a_i\) and \(b_i\).

Your output must satisfy:

  • \(P = a^{b_1}_1a^{b_2}_2a^{b_3}_3\cdots a^{b_K}_K\) (or equivalently, \(P = \prod_{i=1}^{K}{a^{b_i}_i}\))
  • \(1 \le a_i, b_i \le 10^{18}\)
  • \(0 \le K \le 10^6\)

It is guaranteed that the number of possible orderings is expressible in this form.

제한

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

예제 입력 1

5 2
1 7
3 7
6 2
7 4
6 7
5 6

예제 출력 1

3 1
4 1

Figure 2: Possible maps of the island for sample testcase 1

The 12 distinct configurations above are the only possible orderings of the towns around the coast. As such, the number of possible orderings, P, is 12. Since 31 × 41 = 12, the output is correct. Note that there are other ways to represent 12 in the output, and those outputs will also be judged as correct.

예제 입력 2

5 1
6 1
6 2
6 3
6 4
6 5

예제 출력 2

3 1
2 3

Figure 3: A possible map for sample testcase 2

There are 24 possible orderings of the island in this input. As such, the number of possible orderings, P, is 24. Since 31 × 23 = 24, the output is correct. Note that there are other ways to represent 24 in the output, and those outputs will also be judged as correct.

예제 입력 3

6 3
7 1
7 2
8 3
8 4
9 5
9 6
7 8
9 8

예제 출력 3

24 1

Figure 4: A possible map for sample testcase 3

There are 24 possible orderings of the island in this input. As such, the number of possible orderings, P, is 24. Since 241 = 24, the output is correct. Note that there are other ways to represent 24 in the output, and those outputs will also be judged as correct.