题目描述

你有一棵包含 $n$ 个节点的树，每条边的长度为 1，并且每条边都有一个颜色，可能是黑色或白色。你可以执行若干次操作，每次选择一条简单路径，反转路径上所有边的颜色（黑色变为白色，白色变为黑色）。

在进行这些操作后，某些边需要达到特定的颜色要求。你的目标是最小化操作的次数，并在操作次数最小时，最小化操作路径的总长度。

输入格式

第一行，一个正整数 $n$。

接下来 $n − 1$ 行，每行四个整数 $a, b, c, d$：

• 树中有一条边连接 $a$ 和 $b$。

• $c$ = 0, 1 表示初始颜色为白色、黑色。

• $d$ = 0, 1, 2 表示最终要求为白色、要求为黑色、没有要求

输出格式

输出一行，两个整数，表示最小操作数、操作数最小时的最小路径长度和。

样例1

5
2 1 1 0
1 3 0 1
2 4 1 2
5 2 1 1

1 2

路径为2 1 3

样例2

3
1 3 1 2
2 1 0 0

0 0

样例3

6
1 3 0 1
1 2 0 2
2 4 1 0
4 5 1 0
5 6 0 2

1 4

数据范围