题目描述

作为一名间谍，你的任务是确定国家之间运送的货物。每箱货物在驶离出口国后，都会被导向至少一个中间港口。在所有的港口，货物都储存在仓库之中，所以你没法从出口国到进口国追踪特定的箱子。卫星照片告诉你每条航道上每个方向运输了多少箱货物。同时你还知道这些箱子都走最短路。 你的任务是确定指定的两个国家之间的最大可能货运量和最小可能货运量，以箱数记。货运网络可以看作是一棵无根树，其中国家是叶子节点，中间港口是中间节点。同时你了解到，每箱货物一旦到达离开港口，绝对不会折返原路。

如上图所示，有 $6$ 个国家，标号为 $1,2,4,5,7,9$ ，还有三个港口，标号为 $3,6,8$ 。虽然从 $1$ 号国家到 $4$ 号国家的路径上的每条边都通过了至少 $4$ 箱货物，但是实际上没法从 $1$ 号国家到 $4$ 号国家输送 $4$ 箱货物。非要如此，则在 $6$ 号港口会有 $1$ 箱从 $2$ 号国家的送来的货物被迫折返，如是不可。

输入格式

输入的第一行有一个整数 $n (3 \le n \le 10000)$ ：节点个数（包括了国家和中间港口）。

之后的 $n-1$ 行每行有四个整数 $a, b, c1, c2$ , $(1 \le a, b \le n , 0 \le c1, c2 \le 1000)$ ，表示从 $a$ 到 $b$ 的航道上有 $c1$ 箱货物，从 $b$ 到 $a$ 的航道上有 $c2$ 箱货物。

最后一行是两个整数 $fr$ 和 $to$ , $(1 \le fr, to \le n, fr \ne to)$ ：指定的两个国家，分别是出口国和进口国。每行的整数由单个空格隔开。 输入数据满足 $Kirchhoff$ 定律：在每个港口输入的箱数等于输出的箱数。虽说满足此定律并不意味着必然存在一个输出方案满足输入的描述，但是，输入数据经过特殊设计，确保至少一个方案的存在性。

输出格式

输出一行，包括两个由单个空格分隔开的整数，分别为从 $fr$ 到 $to$ 的最小和最大可能运输箱数，要求满足给定的数据。

9
1 6 4 1
2 6 2 1
6 3 4 0
7 3 1 1
9 3 1 1
3 8 6 2
8 4 4 1
8 5 2 1
1 4

1 3

数据规模与约定

$50\%$ 的数据中 $n \le 10$ ,

$100\%$ 的数据中 $n \le 10000$ 。

题目来源

2011福建集训