## TSOC '15 Contest 2 #4 - Dungeon Crawling

View as PDF

Points: 10
Time limit: 0.6s
Java 8 1.0s
PyPy 2 1.0s
PyPy 3 1.0s
Memory limit: 391M
Java 8 293M
PyPy 2 293M
PyPy 3 293M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The team refuses to risk it in the caves any further, so they decide to hire others to traverse the caves instead. They purchase numerous seasoned ex-convicts from ram.tin.gz and kayv.bon.g.

Using his psychic powers, Mehdi charts out a map of the caves, which are comprised of rooms. Cave rooms are numbered from to , inclusive. Rooms are connected by one-way paths. of these rooms are entrances , are destinations and some are neither. Destinations do not lead to other rooms but are reachable from other rooms, while entrances have no room which leads to them but have outward paths to other rooms. Mr. Benum is known to be held prisoner in one of the destinations, and the team members can each start from any entrance. There are no cyclic paths. Max has the ex-convicts split up, such that each ex-convict traverses a unique path from an entrance to a destination.

As the organizer of this foray into danger, Max would like to know the following:

• How many ex-convicts are needed to take all unique paths?
• What is the minimum number of cave rooms that we have to travel through to reach each of the destination rooms (individually) where Mr. Benum may be held?

#### Input Specification

The first line will contain the integers , separated by single spaces. Each of the next lines contain two space-separated integers , indicating a unidirectional (one-way) path from to .

#### Output Specification

First line: The total number of team members required to take every possible path through the cave (if one team member can only follow one path), modulo .

Second line: space-separated integers, with the integer representing the minimum number of different cave rooms that one must pass into to reach the destination room.

#### Sample Input

6 6
0 1
1 2
2 4
4 5
1 3
2 3

#### Sample Output

3
3 5

Where do we get E and D? It's not in the input specification.