I - 首都
解説
/
実行時間制限: 2 sec / メモリ制限: 128 MB
Problem Statement
閉路のない連結な有向グラフが与えられる.(有向グラフが連結であるとは,これを無向グラフとした時に連結であるという事である.)
このグラフに対して一つの頂点を選んで首都 $s$ を定めたい.
$T(v)$ = "$v$ から全ての点を到達可能にするために必要な「辺の反転」操作の回数の最小値"とする.
ただし,「辺の反転」とは,頂点 $v,u$ に関して $(v,u)$ に張られていた有向辺を削除して $(u,v)$ に張り直すことである.
頂点 $s$ が首都であるとは任意の頂点 $v$ に対して, $T(s)\leq T(v)$ が成立することである.
首都であるような頂点をすべて列挙して答えよ.
Input
入力は以下のような形式で $M+1$ 行で与えられる.
$N$ $M$
$a_1$ $b_1$
:
:
$a_M$ $b_M$
- 1行目には二つの整数 $N$, $M$ が与えられ,与えられるグラフは $N$ 頂点 $M$ 辺であることを表す.
- 2行目から $M+1$ 行目にはそれぞれ二つの整数 $a_i, b_i$ が与えられ,$a_i$ から $b_i$ に有向辺が張られていることを表す.
Constraints
- $1 \leq N \leq 10{,}000$
- $0 \leq M \leq 100{,}000$
- $0 \leq a_i \leq N-1 $
- $0 \leq b_i \leq N-1 $
- $a_i \neq b_i$
- $i \neq j $ ならば $(a_i, b_i) \neq (a_j, b_j)$
- 与えられるグラフは連結で閉路はない.
- 与えられるグラフに対して,入次数が0である頂点の個数は50以下である.
Output
以下の形式で2行で出力せよ.
$cnum$ $cost$
$c_1$ $c_2$ ... $c_{cnum}$
- 1行目には二つの整数 $cnum$, $cost$ を空白区切りで出力せよ.
- 2行目には $cnum$ 個の整数 $c_i$ を空白区切りで出力せよ.
- 変数の意味は以下の通りである.
- $cnum$ : 首都の性質を満たす頂点数
- $cost$ : 首都となる頂点 $v$ に対する $T(v)$ の値
- $c_i$ : 首都の性質を満たす頂点を番号に関して昇順に並べた時,$i$ 番目の頂点番号
Sample Input 1
3 2 0 1 2 1
Output for the Sample Input 1
2 1 0 2
- 頂点0を首都とするときには辺(2,1)を反転すれば,(0,1), (1,2)の辺を持つグラフができるので1が答え.
- $T(0)=1$,$T(1)=2$,$T(2)=1$である.
Sample Input 2
5 4 0 1 2 1 2 3 4 3
Output for the Sample Input 2
3 2 0 2 4
Sample Input 3
5 5 0 1 1 2 3 2 3 4 4 1
Output for the Sample Input 3
2 1 0 3