给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。
小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。
第一行是两个整数，分别表示该图的顶点数 $n$ 和边数 $m$。
傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。
这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有 $n$ 个地方，那么最快的方法当然是修复 $n-1$ 条道路将这 $n$ 个地方都连接起来。 幻想乡这 $n$ 个地方本来是连通的，一共有 $m$ 条边。现在这 $m$ 条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第 $i$ 条边所需要的时间为 $e_i$。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个 $e_i$ 会是一个 $0$ 到 $1$ 之间均匀分布的随机实数。并且所有 $e_i$ 都是完全独立的。
现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那 $n-1$ 条边，同时开始修复，那么修复完成的时间就是这 $n-1$ 条边的 $e_i$ 的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 $e_i$ 的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？
给定一个无向连通图，其节点编号为 $1$ 到 $N$，其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算“XOR 和”时也要被重复计算相应多的次数。
直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 $1$ 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 $N$ 号节点为止，便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。
输入文件的第一行是用空格隔开的两个正整数 $N$ 和 $M$，分别表示该图的节点数和边数。紧接着的 $M$ 行，每行是用空格隔开的三个非负整数 $u,v$ 和 $w$。$(1\le u,v\le N$，$0\le w\le 10^9)$，表示该图的一条边 $(u,v)$，其权值为 $w$。输入的数据保证图连通。
为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 $n (n \le 10^9)$ 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？
判断两棵树是否同构的伪代码如下：
$$ \def\arraystretch{1.2} \begin{array}{ll} \hline \textbf{算法 1}&\text{Check}(T1,T2) \ \hline 1&\textbf{Require: }\text{ 两棵树的节点}T1,T2\ 2&\qquad\textbf{if}\ \ T1=\text{null}\textbf{ or }T2=\text{null}\textbf{ then }\ 3&\qquad\qquad\textbf{return}\ \ T1=\text{null}\textbf{ and }T2=\text{null}\ 4&\qquad\textbf{else}\ 5&\qquad\qquad\textbf{return}\ \text{Check}(T1\to\mathit{leftson},T2\to\mathit{leftson}) \ & \qquad\qquad\qquad \textbf{ and }\text{Check}(T1\to\mathit{rightson},T2\to\mathit{rightson})\ 6&\qquad\textbf{endif}\ \hline \end{array} $$
“A fight? Count me in!” 要打架了，算我一个。
“Everyone, get in here!” 所有人，都过来！
小 Y 是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。
SHOI2012 D1T3
一棵含 $n$ 个叶结点的二叉树可以通过如下方式生成。初始时只有根结点。首先，将根结点展开（本题中的“展开”是指给一个叶结点添上左、右两个子结点）：
[a]
你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出 $k$ 次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。
宝物一共有 $n$ 种，系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。也就是说，即使前 $(k-1)$ 次系统都抛出宝物 $1$（这种情况是有可能出现的，尽管概率非常小），第 $k$ 次抛出各个宝物的概率依然均为 $\frac{1}{n}$。
获取第 $i$ 种宝物将得到 $p_i$ 分，但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $s_i$。只有当 $s_i$ 中所有宝物都至少吃过一次，才能吃第 $i$ 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，$p_i$ 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。
假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？
甲乙两个人玩取石子游戏。他们面前有一堆共 $n$ 个石子，然后由甲先手，两人轮流从中取走石子：甲第一次取走的个数不能超过 $k$，接下来每个人取走的个数不能超过上一个人刚刚取走个数的 $2$ 倍。每人每次必须至少取一个石子。取走最后一个石子的人失败，另一方获胜。现在已知 $k$，请你求出在 $1$ 到 $N$ 中有多少整数 $n$ 使得甲在 $n$ 颗石子的游戏中有必胜策略。
多组数据。
第一行一个正整数 $T$ 表示数据组数。