题目描述

给出一张 $n$ 个点，$m$​ 条边的有向图与一个中心点 $r$。

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

保证中心点 $r$​，它可以到达所有结点。

你需要求出：

• 每个点能够到达的结点数量（包括自己）；
• 最少加入多少条边，能使得所有顶点之间均可以相互 到达。

输入格式

第一行三个整数 $n,m,r$。

接下来 $m$ 行，每行两个数 $u,v$ 表示存在一条有向边 $u\to v$。

输出格式

第一行 $n$ 个整数，第 $i$ 个整数表示结点 $i$ 能到达的结点数量。

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

接下来 $k$ 行，每行两个数 $x,y$ 表示需要添加一条有向边 $x\to y$。

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

数据规模与约定

对于 $100\%$​ 的数据，$1\leq n\leq 10^5$，$1\leq m\leq 5\times 10^5$。