Longest Perfect Path in a DAG

We are given a directed acyclic graph (DAG) with n nodes and m edges. Each edge has two attributes: a weight and a length.

A pair of positive integers \(a\) and \(b\) is called a perfect pair if their product is a perfect power with exponent at least 2, i.e. there exists a positive integer \(c\) and an integer \(k\) (\(k\ge2\)) such that \[ a \times b = c^{k}. \]

A perfect path in the graph is defined as follows:

• If the path consists of exactly one edge, it is a perfect path.
• If the path contains \(p\ (p\ge2)\) edges represented as \(e_1, e_2, \ldots, e_p\), then for every adjacent pair \(e_i\) and \(e_{i+1}\) (for \(1 \le i \le p-1\)), the weights \(w_i\) and \(w_{i+1}\) must form a perfect pair, i.e. \[ w_i \times w_{i+1} = c^{k}\,\text{ for some } c \in \mathbb{Z}^+,\; k\ge2. \]

The length of a path is the sum of the lengths of its edges. Your task is to compute the maximum length of any perfect path in the graph.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 10^5)\), denoting the number of nodes and edges respectively. Each of the following \(m\) lines contains four positive integers \(u, v, w, l\), where \(u\) and \(v\) are the start and end nodes of an edge, \(w\) is the weight and \(l\) is the length of that edge. It is guaranteed that the graph is a DAG.

outputFormat

Output a single integer representing the maximum length of a perfect path in the graph. If there is no edge, output 0.

sample

3 3
1 2 2 3
2 3 8 5
1 3 2 4

8