w

w.cpp/in/out

• 时间限制：1.0s
• 空间限制：512MB

题目描述

有一棵 $n$ 个节点的树，每条边长度为 1，颜色为黑或白。

可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。

对于某些边，要求在操作结束时为某一种颜色。

给定每条边的初始颜色，求最小操作数，以及满足操作数最小时，最小的操作路径长度和。

输入格式

从文件 w.in 中读入数据。

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

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

• 树中有一条边连接 $a$ 和 $b$。
• $c = 0, 1$ 表示初始颜色为白色、黑色。
• $d = 0, 1, 2$ 表示最终要求为白色、要求为黑色、没有要求。

输出格式

输出到文件 w.out 中。

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

样例 1 输入

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

样例 1 输出

1 2

样例 1 解释

操作路径 $\{2, 1, 3\}$。

样例 2 输入

3
1 3 1 2
2 1 0 0

样例 2 输出

0 0

样例 3 输入

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

样例 3 输出

1 4

数据范围

保证给出的图为一棵树，有 $n \in [1, 10^5]$，$a, b \in [1, n]$，$c \in \{0, 1\}$，$d \in \{0, 1, 2\}$。