Državno natjecanje iz informatike 2021. / Druga podskupina (3. i 4. razred) – drugi dan natjecanja - 2. zadatak

Zadan je usmjereni graf u kojemu iz svakog vrha izlazi točno jedan brid u neki drugi vrh.

Koliki je najmanji broj vrhova koje iz toga grafa treba obrisati tako da u grafu ne ostane nijedan put duljine dva; drugim riječima, tako da ne postoje neka tri (ne nužno sva različita) vrha a, b, c s bridovima a → b i b → c?

Dodatno, na koliko načina možemo obrisati taj najmanji broj vrhova da bismo ispunili navedeni uvjet?

Ulazni podaci

U prvom je retku prirodan broj n (3 ≤ n ≤ 100 000), broj vrhova grafa. Vrhovi su označeni brojevima od 1 do n.

U i-tom od idućih n redaka prirodan je broj j (i 6= j) koji predstavlja brid i → j.

Izlazni podaci

U prvi redak ispišite traženi najmanji broj vrhova koji treba obrisati.

U drugi redak ispišite traženi broj načina, točnije njegov ostatak pri dijeljenju s 1 000 000 007.

Primjer zadatka

Ulaz

4
3
3
4
3

Izlaz

1
2

Objašnjenje

Pojašnjenje prvog probnog primjera: Možemo obrisati vrh 3. Alternativno, možemo obrisati vrh 4.

Ulaz

5
4
5
4
2
1

Izlaz

2
5

Objašnjenje

Pojašnjenje drugog probnog primjera: Možemo obrisati sljedeće parove vrhova: (1, 2), (1, 4), (2, 4),

(2, 5), (4, 5).

Ulaz

6
2
1
2
6
4
5

Izlaz

2
6

Objašnjenje

Pojašnjenje trećeg probnog primjera: Možemo obrisati sljedeće parove vrhova: (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6).