The Capital

時間制限 : 2 sec, メモリ制限 : 131072 KB

閉路のない連結な有向グラフが与えられる.(有向グラフが連結であるとは,これを無向グラフとした時に連結であるという事である.)

このグラフに対して一つの頂点を選んで首都 s を定めたい.

T(v) = "v から全ての点を到達可能にするために必要な「辺の反転」操作の回数の最小値"とする.

ただし,「辺の反転」とは,頂点 v, u に関して (v, u) に張られていた有向辺を削除して (u, v) に張り直すことである.

頂点 s が首都であるとは任意の頂点 v に対して, T(s) ≤ T(v) が成立することである.

首都であるような頂点をすべて列挙して答えよ.

Input

入力は以下のような形式で M + 1 行で与えられる.

N M
a1 b1
:
aM bM
  • 1 行目には二つの整数 N, M が与えられ,与えられるグラフは N 頂点 M 辺であることを表す.
  • 2 行目から M + 1 行目にはそれぞれ二つの整数 ai, bi が与えられ,ai から bi に有向辺が張られていることを表す.

Constraints

  • 1 ≤ N ≤ 10,000
  • 0 ≤ M ≤ 100,000
  • 0 ≤ aiN − 1
  • 0 ≤ biN − 1
  • ai ≠ bi
  • i ≠ j ならば (ai, bi) ≠ (aj, bj)
  • 与えられるグラフは連結で閉路はない.
  • 与えられるグラフに対して,入次数が 0 である頂点の個数は 50 以下である.

Output

以下の形式で2 行で出力せよ.

cnum cost
c1 c2 . . .  ccnum
  • 1 行目には二つの整数 cnum, cost を空白区切りで出力せよ.
  • 2 行目には cnum 個の整数 ci を空白区切りで出力せよ.
  • 変数の意味は以下の通りである.
         − cnum : 首都の性質を満たす頂点数
         − cost : 首都となる頂点 v に対する T(v) の値
         − ci : 首都の性質を満たす頂点を番号に関して昇順に並べた時,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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 4, Tokyo, Japan, 2014-09-15
http://acm-icpc.aitea.net/
http://jag2014summer-day4.contest.atcoder.jp/