[Ceoi2012]network
时间限制：10s 空间限制：128MB
题目描述
给出一个有向图，有n个顶点，m条边。
如果从p到q有一条唯一的路径，则称顶点p可以到达顶点q。
图中有一个中心点r，它可以到达所有顶点。
任务
(A)求出每个顶点能够到达的顶点数量(包括自身)
(B)最少加多少条边，使得所有顶点之间均可以相互到达
输入格式
第1行:3个整数n(1 n 100,000) , m(1 m 500,000),。顶点编号从1..n编号，有向边编号从1..m编号，R(1 R<n)是图的中心点编号。
接下来m行，每行2个整数，分别表示一条有向边的开始到结束点
输出格式
第1行: 1个整数，分别表示第i个整数可到达的顶点数量。
第2行：1个整数，表示最少需要添加的边的数量X。
接下来X行，每行2个整数，表示添加的一条有向边。
样例输入
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 6 11 6 1 6 1 4 4 4 1 5 1 3 5 4 7 6 11 9 8 3
提示
没有写明提示
题目来源
鸣谢Ydc提供SPJ