問題
背景
Ikta,一名图形绘制工匠,每天研究如何绘制图形,以便尽可能忠实地按照客户要求绘制颜色。 今天,当我用两种颜色绘制顶点时,我决定关注两端顶点具有不同颜色的边的数量。
課題
n 顶点和 n 存在一个由书本边组成的连通图。该图中不存在两端都连接到同一个顶点的边,并且存在 2 一个顶点之间不能有多条边。
将此图的所有顶点绘制为红色或蓝色。此时,至少应该有一个顶点涂成红色,一个或多个顶点涂成蓝色。当满足这样的条件进行绘制时,求出两端顶点分别绘制的边的最小和最大条数。
这个问题也适用于最小割和最大割(日文版维基百科 这相当于查找的问题。
配点
100
入力
输入按以下格式给出。
n a_1 b_1 : a_n b_n
1 直线上的顶点和边数 写入 n (3 ≤ n ≤ 100,000) 。 代表第 2 从行 n+1 行中, 一个整数,表示第2 整数 a_i, b_i 并且顶点 a_i 和顶点 这表明有一条边连接b_i 。
制約
- 3 ≤ n ≤ 100,000
- 1 ≤ a_i,b_i ≤ n
- 不存在两端都连接到同一顶点的边。
- 两个顶点之间不存在重边。
出力
两端顶点分别绘制的边的最小数量 min 和最大值 MAX 以空格分隔 1 行输出。
入出力例
入力例1
4 1 2 2 3 3 1 1 4
出力例1
1 3