Kabar Berantai
Hitung berapa hari sampai sebuah kabar sampai ke semua orang.
Di grup kelas, kabar libur menyebar lewat pertemanan. Pada hari ke-0 hanya satu orang yang tahu. Setiap hari, orang yang sudah tahu memberi tahu semua temannya. Kapan semua orang tahu?
Masukan
Baris pertama berisi N (1 sampai 10000) banyaknya orang, M (1 sampai 20000) banyaknya pasangan teman, dan S orang pertama yang tahu. Orang dinomori 1 sampai N. M baris berikutnya masing-masing berisi dua orang yang berteman.
Keluaran
Bila semua orang akhirnya tahu, tampilkan Semua tahu pada hari ke-X. Bila ada yang tidak pernah tahu, tampilkan K orang tidak pernah mendapat kabar.
Contoh masukan dan keluaran
Contoh 1
Masukan
6 6 1 1 2 1 3 2 4 3 4 4 5 5 6
Keluaran
Semua tahu pada hari ke-4
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Simpan daftar teman setiap orang. Dengan begitu kamu bisa langsung melihat teman siapa pun tanpa memeriksa semua pasangan.
Petunjuk 2
BFS dari orang pertama menelusuri teman hari demi hari. Hari seseorang mendapat kabar adalah jaraknya dari orang pertama.