[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