分数: 300 点
问题陈述
您正在玩以下游戏。
- 你有一棵树 N = 100 顶点和 M (= N-1 = 99) 边,以及一个整数 X。的顶点 T 编号自 1 to N.对于每个 i (1 \leq i \leq M),顶点 a_{i} 和 b_{i} 用边连接。
- 你制作图表 G 通过添加 A (>= 0) 树的边 T 一一这样 G 没有多重边和自环。
- 中的边缘 G 也存在于 T 消失并且 G 已重命名 G' 在顶点编号之后 G 已排列。 G' 有 N = 100 顶点和 A 边缘。中的顶点 G' 编号自 1 to N,并且对于每个 i (1 \leq i \leq A), c_{i} 和 d_{i} 用边连接。
- 树的信息 T,图表 G和整数 X 从你的记忆中消失。
- 你看图 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,您的输出是正确的。
法官
评审程序按以下步骤运行。
- 启动两个进程来运行编码和解码阶段提交的程序。
- 编码阶段的输入被提供给编码过程。请注意
未给出
EOF。 - 等待编码过程打印编码阶段的输出并且编码过程完全退出。
- 如果图 编码阶段输出生成的 G包含多条边和自环或者顶点数不在范围内: [1, N],答案是错误的。
- 解码阶段的输出被提供给解码过程。请注意
EOF。 - 等待解码过程打印解码阶段的输出并且解码过程完全退出。
- 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