logo AlgoBeat OnlineJudge
登录 注册

#102858. [BZOJ 2858] [Ceoi2012]network

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给出一张 个点,​ 条边的有向图与一个中心点

​ 可以 到达 ​ 当且仅当从 ​ 可以走到 ​​​ 且不存在两个没有交集的边集可以让 走到

保证中心点 ​,它可以到达所有结点。

你需要求出:

  • 每个点能够到达的结点数量(包括自己);
  • 最少加入多少条边,能使得所有顶点之间均可以相互 到达

输入格式

第一行三个整数

接下来 行,每行两个数 表示存在一条有向边

输出格式

第一行 个整数,第 个整数表示结点 能到达的结点数量。

第二行一个整数 ,表示最少需要添加的边的数量。

接下来 行,每行两个数 表示需要添加一条有向边

样例

样例输入 #1

11 12 3 
3 2 
2 1 
2 4 
4 5 
4 6 
6 2 
6 7 
3 8 
8 9 
9 10 
9 11 
10 8

样例输出 #1

1 6 11 6 1 6 1 4 4 4 1
5 
1 3 
5 4 
7 6 
11 9 
8 3

数据范围与提示

对于 ​ 的数据,