I - 首都

Time Limit: 2 sec / Memory Limit: 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