## Claire Elstein

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
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

Claire is secretly a fan of eroge. When she thinks nobody is looking, she boots up her laptop and starts playing...

We can model an eroge as a directed acyclic graph (DAG) with edges with vertices numbered from to . Each vertex is a choice point. Choice points are connected by edges, each taking up exactly 1 unit of time to advance.

Claire would like to play through all possible routes of her eroge. She may start at any choice point that does not have any other choice point leading to it. Help her compute the total time needed to play through the whole game!

In other words, you should compute the sum of the lengths of all paths from a vertex with indegree 0 to a vertex with outdegree 0. It is possible for the graph to have duplicate edges. If there are any isolated choice points (indegree and outdegree both 0), you should treat them as if they would be finished instantly.

#### Input Specification

The first line will have and separated by a single space, the number of vertices and edges, respectively.

The next lines will have a pair , separated by a single space, denoting a directed edge from to .

#### Output Specification

The first and only line of output should have the answer modulo , as this number can otherwise be very large.

#### Sample Input 1

3 6
1 2
1 2
1 2
1 2
1 2
2 3

#### Sample Output 1

10

#### Sample Input 2

8 14
1 3
1 4
1 5
2 3
2 4
2 5
3 6
3 7
4 6
4 7
5 6
5 7
6 8
6 8

#### Sample Output 2

48

• commented on Jan. 11, 2020, 4:10 p.m.

• commented on July 20, 2019, 3:35 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Sept. 9, 2016, 5:40 p.m.

Missing space before .

• commented on April 2, 2016, 3:10 p.m.

parents thought it was porn....

• commented on April 3, 2016, 5:31 p.m.

What image? Oh wait I adblocked it.

• commented on April 3, 2016, 5:25 p.m.

It's from Seirei Tsukai no Blade Dance, which is supposed to be 13+.

• commented on April 3, 2016, 10:44 a.m.

Eh, why your parents are so suspicious of you? In that case, you should not solve questions like Rabbit/Cat/Dog girls.