E. TOF

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Өнөөдөр Пари Аря-д нэгэн сонирхолтой графын бодлого өгчээ. Аря уг бодлогын нэгэн бүрэн оновчтой биш бодолтыг бичсэн бөгөөд учир нь тэрээр бүрэн оновчтой биш бодолтыг оновчтой бодолт болгох өөрийн чадвартаа найджээ. Тодруулбал бүрэн оновчтой биш гэдэг нь түүний бодолт дутуу бөгөөд тэрээр уг бодолтоо оновчтой болгохын тулд ихээхэн оролдсон ба ингэснээр түүний бичсэн код нь маш эмх замбараагүй болсон гэсэн үг юм! Тэрээр хугацааны хязгаарлалтын асуудлыг шийдэхээр дахин дахин оролдсоор байгаа боловч ахин дахин бүтэлгүйтсээр байв. Гэнэт түүний толгойд нэгэн гайхалтай санаа орж иржээ!

Доор эмх замбараагүй код хэрхэн харагддаг болохыг дүрслэв:

dfs(v)  
{  
     set count[v] = count[v] + 1  
     if(count[v] < 1000)  
     {  
          foreach u in neighbors[v]  
          {  
               if(visited[u] is equal to false)  
               {  
                    dfs(u)  
               }  
               break  
          }  
     }  
     set visited[v] = true  
}  

main()  
{  
     input the digraph()  
     TOF()  
     foreach 1<=i<=n  
     {  
          set count[i] = 0 , visited[i] = false  
     }  
     foreach 1 <= v <= n  
     {  
          if(visited[v] is equal to false)  
          {  
               dfs(v)  
          }  
     }  
     ... // And do something cool and magical but we can't tell you what!  
}

Тэрээр танаас dfs функцийг дуудах тоо нь хамгийн бага байхаар бичсэн кодын ажиллах хугацааг тохируулах TOF функцийг бичиж өгөхийг хүсжээ. Оролт нь чиглэлтэй граф байх бөгөөд TOF функц дээр та орой бүрийн хөршүүдийн бүртгэл дээрх графын ирмэгүүдийг дараалалд оруулах ёстой юм.

dfs функцийн дуудалтын тоо нь орой бүрийн хөршүүдийн дараалалд оруулалтаас хамаарна.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 5000$) өгөгдөх ба эдгээр нь харгалзан оролтод өгөгдөх графын оройны тоо болон чиглэлтэй ирмэгүүдийн тоог илэрхийлнэ.

Дараагийн $m$ мөрийн мөр болгонд хос бүхэл тоо $u_{i}$ болон $v_{i}$ ($1  ≤  u_{i},  v_{i}  ≤  n$) өгөгдөх ба эдгээр нь оролтод өгөгдөх граф дээр гэсэн чиглэлтэй ирмэг байгааг илэрхийлэх юм.

Та граф нь ямар нэгэн өөртөө-гогцоо агуулаагүй байна гэж үзэх ба дараалалд ороогүй ямар ч хос оройнуудын хооронд хамгийн ихдээ нэг ирмэг байна гэж үзнэ.

Гаралт

Ирмэгүүдийг дараалалд оруулж чадах dfs функцийн дуудалтын боломжит хамгийн цөөн тоог илэрхийлэх ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 3
1 2
2 3
3 1
Гаралт
2998
Оролт
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
Гаралт
3001
Сэтгэгдлүүдийг ачааллаж байна...