LUTRIJA - LUTRIJA
You are given a cactus graph of N nodes and M edges.
Compute number of simple paths of length L, for each L between 1 and N, modulo 109 + 7. Here path length is number of nodes on it.
Input
First line consists of two integers, N (1 <= N <= 4000) and M (0 <= M <= 100 000).
Each of next M lines consists of two integers a and b (1 <= u < v <= N) which represents bidirectional edge between nodes u and v.
Every pair (u, v) appears at most once in edges list.
Note: graph need not be connected.
Output
Output N integers in one line as described above.
Example
Input: 3 3
1 3
2 3
1 2 Output: 3 6 6
hide comments
[Rampage] Blue.Mary:
2022-01-02 14:39:43
A semi-brute-force solution works. The time complexity seems to be O(N^2). |
|
Daniel Le:
2016-01-17 12:29:28
Is a cycle considered a simple path for this problem? |
|
Alex Anderson:
2015-11-24 07:01:27
One of those input limits is not like the other ;) |
|
Mitch Schwartz:
2015-11-04 18:56:05
@miodziu: It should mean that there do not exist 3 distinct simple paths P1, P2, P3 between a and b with corresponding sets of nodes S1, S2, S3 such that S1 ∩ S2 = S1 ∩ S3 = S2 ∩ S3 = {a, b}. Last edit: 2015-11-04 19:18:24 |
|
miodziu:
2015-11-04 17:06:43
My English isn't very well and I can't understand this sentence:
|
Added by: | Ivan Katanic |
Date: | 2015-10-30 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | Croatian ACM contest 2015 |