LUTRIJA - LUTRIJA

no tags 

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:

"For every pair of different nodes (a, b) it's impossible to find 3 nodes-disjoint (except for nodes a and b) simple paths between them."

Can anyone explain?

EDIT: Now it's clear. Thanks Mitch.

Last edit: 2015-11-06 13:08:21

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