传统题 1000ms 256MiB

*L7修改图的边

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定包含n个顶点,n-1条边的有向图,顶点编号从0到n-1,若要使所有顶点均能到达0号点,请问最少需要修改几条边的方向。

Format

Input

第一行包含一个整数n,表示顶点的数量; 接下来n-1行,每行包含两个整数x,y,表示有一条有向边由顶点x指向顶点y,整数之间以一个空格隔开; 数据保证存在答案。

测试范围: 测试点1~10:1<=n<=10000,0<=x,y<=n。

Output

一个整数,表示要使所有顶点均能到达0号点,请问需要修改几条边的方向。

Samples

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

2024秋学期西门第30次课0107

未参加
状态
已结束
规则
IOI
题目
10
开始于
2025-1-7 16:45
结束于
2025-1-16 0:45
持续时间
200 小时
主持人
参赛人数
8