← 返回题目列表

AtCoder · kupc2017_g

G. 编码/解码 2017

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

您正在玩以下游戏。

  1. 你有一棵树 N = 100 顶点和 M (= N-1 = 99) 边,以及一个整数 X。的顶点 T 编号自 1 to N.对于每个 i (1 \leq i \leq M),顶点 a_{i} 和 b_{i} 用边连接。
  2. 你制作图表 G 通过添加 A (>= 0) 树的边 T 一一这样 G 没有多重边和自环。
  3. 中的边缘 G 也存在于 T 消失并且 G 已重命名 G' 在顶点编号之后 G 已排列。 G' 有 N = 100 顶点和 A 边缘。中的顶点 G' 编号自 1 to N,并且对于每个 i (1 \leq i \leq A), c_{i} 和 d_{i} 用边连接。
  4. 树的信息 T,图表 G和整数 X 从你的记忆中消失。
  5. 你看图 G' 并声明一个整数 Y。如果 X = Y,你赢了。

即使有任何一棵树,你也想赢得上述游戏 T 和整数 给出了 X 。 给定树 T 和整数 给出了 X,查找如何添加 A 边缘到 T,然后给出生成的 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 是整数。

输入和输出

这个问题有编码和解码阶段,每个阶段都是独立执行的。

在编码阶段,你采取树 T 和整数 给出了 X,并找到如何向树添加边 T。在解码阶段,您获取生成的图 G',并找到整数 Y.

输入(编码相位)

在编码阶段,输入由标准输入按以下格式给出:

字符串 encode 在第一行给出。

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

输出(编码相位)

在编码阶段,您必须打印 A+1 行。

打印 A 在第一行。 然后,打印顶点 i-th (1 \leq i \leq A) 在以下内容上添加了边缘 i第行,中间有一个空格。

输入(解码阶段)

在解码阶段,输入由标准输入按以下格式给出:

字符串 decode 在第一行给出。

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

输出(解码阶段)

打印 Y。如果 X = Y,您的输出是正确的。

法官

评审程序按以下步骤运行。

  1. 启动两个进程来运行编码和解码阶段提交的程序。
  2. 编码阶段的输入被提供给编码过程。请注意 未给出 EOF 。
  3. 等待编码过程打印编码阶段的输出并且编码过程完全退出。
  4. 如果图 编码阶段输出生成的 G包含多条边和自环或者顶点数不在范围内: [1, N],答案是错误的。
  5. 解码阶段的输出被提供给解码过程。请注意 EOF 。
  6. 等待解码过程打印解码阶段的输出并且解码过程完全退出。
  7. If X = Y,你的程序是正确的,否则是错误的。

注意,如果输出的格式无效,则提交的程序也会被判断为错误。


样本输入 1(编码相位)

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(编码相位)

2
1 2
2 4

样本输入 1(解码阶段)

decode
100 2
49 33
35 49

请注意,中的顶点数 G' 可能与以下的不同 T.

样本输出 1(解码阶段)

382174891210833608