Problem Statement

You are playing the following game.

1. You are given a tree with N = 100 vertices and M (= N-1 = 99) edges, and an integer X. The vertices of T are numbered from 1 to N. For each i (1 \leq i \leq M), vertex a_{i} and b_{i} are connected with an edge.
2. You make graph G by adding A (>= 0) edges to tree T one by one such that G does not have multiple edges and self-loops.
3. The edges in G which also exist in T disappear and G is renamed G' after the numbers of the vertices in G are permutated. G' has N = 100 vertices and A edges. The vertices in G' are numbered from 1 to N, and for each i (1 \leq i \leq A), c_{i} and d_{i} are connected with an edge.
4. The information on tree T, graph G, and integer X disappear from your memory.
5. You look at graph G' and declare an integer Y. If X = Y, you win.

You want to win the above game even if any tree T and integer X are given. Given tree T and integer X, find how to add A edges to T, and then given the generated G', find integer Y to win the game.

Constraints

• N = 100
• M = 99
• T is a tree.
• 1 \leq a_{i}, b_{i} \leq N (1 \leq i \leq M)
• 0 \leq X \leq 10^{18}
• 0 \leq A \leq {}_NC_2-M = 4,851
• 1 \leq c_{i}, d_{i} \leq N (1 \leq i \leq A)
• N, M, A, a_{i}, b_{i}, c_{i}, d_{i}, X are integers.

Input and Output

This problem has encode and decode phases, each of which is executed independently.

In encode phase, you take tree T and integer X, and find how to add edges to tree T. In decode phase, you take the generated graph G', and find integer Y.

Input (encode phase)

In encode phase, input is given from Standard Input in the following format:

String encode is given on the first line.

encode
N M
a_{1} b_{1}
a_{2} b_{2}
:
a_{M} b_{M}
X

Output (encode phase)

In encode phase, you must print A+1 lines.

Print A on the first line. Then, print the vertices of the i-th (1 \leq i \leq A) added edge on the following i-th line, a single space in between.

Input (decode phase)

In decode phase, input is given from Standard Input in the following format:

String decode is given on the first line.

decode
N A
c_{1} d_{1}
c_{2} d_{2}
:
c_{A} d_{A}

Output (decode phase)

Print Y. If X = Y, your output is correct.

Judge

The judging procedure is run in the following steps.

1. Two processes are launched to run the submitted program for the encode and decode phases.
2. The input for the encode phase is given to the process for encoding. Note that EOF is not given.
3. Wait until the process for encoding prints the output of the encode phase and the process for encoding exits completely.
4. If graph G, which is generated by the output of the encode phase, contains multiple edges and self-loops or the numbers of the vertices is not in the range: [1, N], the answer is wrong.
5. The output for the decode phase is given to the process for decoding. Note that EOF is not given.
6. Wait until the process for decoding prints the output of the decode phase and the process for decoding exits completely.
7. If X = Y, your program is correct, otherwise, wrong.

Note that if the formats of the outputs are invalid, the submitted program is also judged as wrong.

Sample Input 1 (encode phase)

encode
100 99
49 74
50 84
78 91
12 14
9 62
54 77
47 88
29 55
52 53
3 53
53 63
33 95
9 57
44 48
3 13
3 73
1 49
62 63
48 53
55 94
50 60
89 95
57 64
75 96
7 48
41 99
44 79
21 94
13 50
42 82
1 16
22 88
19 34
63 87
1 36
14 58
18 56
33 82
12 37
55 84
87 96
12 55
4 76
64 68
38 52
40 50
38 59
47 75
17 32
18 83
20 63
76 92
54 71
34 59
16 89
39 94
2 98
11 85
24 60
28 76
46 70
19 23
41 46
36 40
68 93
15 37
2 68
82 90
4 26
45 90
28 59
43 94
10 44
16 54
65 97
41 51
10 27
96 97
10 86
52 91
5 44
18 28
32 99
67 84
67 100
46 80
55 72
18 80
69 71
6 43
25 71
30 96
8 57
11 88
80 81
19 61
30 35
8 31
42 66
382174891210833608

Sample Output 1 (encode phase)

2
1 2
2 4

Sample Input 1 (decode phase)

decode
100 2
49 33
35 49

Note that the numbers of the vertices in G' may be different from the ones of T.

Sample Output 1 (decode phase)

382174891210833608