← 返回题目列表

AtCoder · utpc2014_c

C. 最小切割和最大切割

中文机器翻译题面 查看原题

問題

背景

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