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
Comments
Where do we get
E
andD
? It's not in the input specification.Last test case seems to have 11 destinations.