题目描述

Artanis 是飞船 Spear of Adun 的指挥官。他需要把一个用单个比特表示的加密消息，从飞船上的计算机发送到 Aiur 星球上的指挥中心计算机。

整个星际计算机网络可以看作一个有向图，包含 $V$ 个节点和 $E$ 条有向边。每条边形如

含义是：计算机 $x$ 可以把消息发送给计算机 $y$；如果发送的是比特 $0$，它被正确传输的概率为 $p_0$；如果发送的是比特 $1$，它被正确传输的概率为 $p_1$。

一次传输被称为正确，当且仅当接收端得到的比特与发送端发出的比特相同。若传输不正确，则比特会翻转。

当某台计算机收到消息后，它会从自己的所有出边中等概率随机选择一条，并沿该边继续转发消息。

请分别求出：

1. 初始发送比特 $0$ 时，最终到达 Aiur 指挥中心后仍为 $0$ 的概率；
2. 初始发送比特 $1$ 时，最终到达 Aiur 指挥中心后仍为 $1$ 的概率。

输入格式

第一行包含两个整数 $V,E$。

接下来 $E$ 行，每行包含四个数：

x y p0 p1

表示一条从 $x$ 到 $y$ 的有向边，以及该边上传输比特 $0$、比特 $1$ 时分别正确的概率。

输出格式

第一行输出发送比特 $0$ 后最终正确到达的概率。

第二行输出发送比特 $1$ 后最终正确到达的概率。

答案与标准答案的绝对误差不超过 $10^{-5}$ 即视为正确。

数据范围与限制

• $1 \le V \le 5000$；
• $0 \le E \le 50000$；
• 对所有边，$0 \le p_0,p_1 \le 1.0$，且输入中的概率最多有两位小数；
• 不存在大小超过 $70$ 的点集，使得该点集中任意两个点互相可达；换句话说，每个强连通分量大小不超过 $70$；
• 节点编号为 $0$ 到 $V-1$；
• 飞船上的计算机编号为 $0$，Aiur 指挥中心编号为 $V-1$；
• 节点 $V-1$ 的出度为 $0$，且所有节点都可以到达 $V-1$；
• 对于任意两个不同节点 $x,y$，至多有一条从 $x$ 到 $y$ 的边，也至多有一条从 $y$ 到 $x$ 的边；
• 不存在自环；
• 对于 $20$ 分测试，图中不存在两个不同节点 $x,y$，使得 $x$ 可达 $y$ 且 $y$ 可达 $x$，即图无环；
• 另有 $40$ 分测试满足 $V \le 100$。

样例

输入

4 3
0 1 1.0 0.5
1 2 0.2 1.0
2 3 0.1 0.0

输出

0.8200000
0.0900000

样例解释

若发送比特 $1$，有一种最终正确到达的过程是：

• 在边 $(0\to 1)$ 上传输错误，概率为 $0.5$，到达节点 $1$ 时变为比特 $0$；
• 在边 $(1\to 2)$ 上传输比特 $0$ 正确，概率为 $0.2$，到达节点 $2$ 时仍为比特 $0$；
• 在边 $(2\to 3)$ 上传输比特 $0$ 错误，概率为 $0.9$，最终又变回比特 $1$。

该过程的概率为

发送比特 $0$ 时可类似计算。