G - encode/decode 2017 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

あなたは以下のようなゲームに参加します。

  1. N = 100 頂点 M (= N-1 = 99) 辺からなる木 T と整数 X が与えられる。T の頂点には 1,2,...,N の番号がついており、各 i (1 \leq i \leq M) について頂点 a_{i} と頂点 b_{i} の間に辺がある。
  2. あなたは、多重辺や自己辺ができないように、T に辺を付け加えることを 0 回以上繰り返してグラフ G を作る。ここで A 本の辺を付け加えたとする。
  3. G から T にあった辺が消え、頂点番号が付け替わったグラフ G' が生成される。G'N = 100 頂点 A 辺からなるグラフで、G' の頂点には 1,2,...,N の番号がついており、各 i (1 \leq i \leq A) について頂点 c_{i} と頂点 d_{i} の間に辺がある。
  4. あなたの記憶から木 T とグラフ G と整数 X の情報が消える。
  5. あなたはグラフ G' を見て、整数 Y を宣言する。X = Y となれば成功となる。

あなたはどのような木 T と整数 X が与えられてもゲームが成功できるようにしたいと思っています。 木 T と整数 X が与えられたとき、辺の付け加え方を求め、そこから手順 3 によって生成されたグラフ G' が与えられたとき整数 Y を求めるプログラムを作成してください。

制約

  • N = 100
  • M = 99
  • T は木である
  • 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 は全て整数である

入出力

この問題には encode フェーズと decode フェーズがあり、それぞれ独立にプログラムが実行される。

ただし、encode フェーズとは木 T と整数 X が与えられたとき、辺の付け加え方を求めることに該当し、deocde フェーズとは手順 3 によって生成されたグラフ G' が与えられたとき整数 Y を求めることに該当する。

入力 (encode フェーズ)

encode フェーズにおいて入力は以下の形式で標準入力から与えられる。

1 行目は文字列 encode が与えられる。

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

出力 (encode フェーズ)

出力は A+1 行からなる。

最初の 1 行に A を出力し、続く A 行の i (1 \leq i \leq A) 行目に、i 回目に付け加える辺の端点の頂点番号を、空白を区切りとして出力せよ。

ただし、encode フェーズの出力が次に示すいずれかの場合には不正解となり、decode フェーズは実行されない。

  • 出力された辺を全て木 T に付け加えたグラフが多重辺や自己辺を含む場合
  • 出力された辺の端点の頂点番号が 1 以上 N 以下でない場合

入力 (decode フェーズ)

decode フェーズにおいて入力は以下の形式で標準入力から与えられる。

1 行目は文字列 decode が与えられる。

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

出力 (decode フェーズ)

Y の値を 1 行で出力せよ。 X = Y であった場合に限り正解となる。

ジャッジ

ジャッジは以下の手順で行われる。

  1. 提出されたプログラムのプロセスを encode 用と decode 用として2つ立ち上げる。
  2. encode 用のプロセスに encode フェーズの入力を与える。ただし、EOF は与えない。
  3. encode 用のプロセスから encode フェーズの適切な出力があり、かつ encode 用のプロセスが終了するまで待機する。
  4. 出力された辺を全て木 T に付け加えたグラフが多重辺や自己辺を含む場合や、出力された辺の端点の頂点番号が 1 以上 N 以下でない場合は誤答とする。
  5. decode 用のプロセスに decode フェーズの入力を与える。ただし、EOF は与えない。
  6. decode 用のプロセスから decode フェーズの適切な出力があり、かつdecode 用のプロセスが終了するまで待機する。
  7. X = Y の場合に限り正答、そうでなければ誤答とする。

また、出力のフォーマットが不正な場合も誤答とする。


入力例1 (encode フェーズ)

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

出力例1 (encode フェーズ)

2
1 2
2 4

入力例1 (decode フェーズ)

decode
100 2
49 33
35 49

G' の頂点番号は元の木 T と異なるものになる可能性があることに注意せよ。

出力例1 (decode フェーズ)

382174891210833608

Score : 300 points

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

Source Name

KUPC2017