AT_kupc2017_g encode/decode 2017
Description
[problemUrl]: https://atcoder.jp/contests/kupc2017/tasks/kupc2017_g
あなたは以下のようなゲームに参加します。
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 $ を求めるプログラムを作成してください。
### Input & Output Format
この問題には encode フェーズと decode フェーズがあり、それぞれ独立にプログラムが実行される。
ただし、encode フェーズとは木 $ T $ と整数 $ X $ が与えられたとき、辺の付け加え方を求めることに該当し、deocde フェーズとは手順 3 によって生成されたグラフ $ G' $ が与えられたとき整数 $ Y $ を求めることに該当する。
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- $ 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 フェーズ)
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
```