Description

Today is Penguin07's birthday, and he decided to build a pathway from National Tsing Hua University (NTHU) to his home as a birthday gift.

We can think of Hsinchu as an N×N grid, where NTHU is located at the coordinate (1, 1) and Penguin07's home is at (N, N). The value h_i,j​ represents the elevation at the grid cell with coordinates (i, j).

Penguin07's construction team needs to build a pathway from NTHU (1,1) to Penguin07's home (N,N). The pathway can be seen as a route within this grid, moving in any of the four cardinal directions (up, down, left, right) from (1, 1) to (N, N).

Considering Penguin07's safety while walking on the pathway, attention must be paid to the elevation differences between consecutive steps. The goal is to establish a pathway with the minimum possible maximum elevation difference. Additionally, under the condition of this minimum maximum elevation difference, the shortest possible path length should be considered.

Please output the minimum value of the maximum elevation difference for such a pathway and, given this minimum elevation difference, the shortest path length.

Input

The first line contains a number n (1 ≤ n ≤ 300), representing the size of the region.

The following n lines each contain n positive integers. Each integer h_{i, j}​ (1 ≤ h_{i, j} ≤ 10⁶) represents the elevation at position (i, j).

Output

Output two lines: the first line should output the minimum value of the maximum elevation difference in the chosen pathway, and the second line should output the length of the shortest path from the top-left to the bottom-right under this maximum elevation difference.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given a directed graph with n vertices and m edges.

How many possible paths start from vertex 1 and end at vertex n?

The given graph is guaranteed to be acyclic (i.e., it has no cycles).

Input

The first input line has two integers n and m: the number of vertices and edges. The vertices are numbered 1, 2, ..., n.

After this, there are m lines describing the edges. Each line has two integers a and b: there is a edge from vertex a to vertex b.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ m ≤ 2 ⋅ 10⁵
• 1 ≤ a, b ≤ n

Output

Print one integer: the number of paths from vertex 1 to vertex n.

Since the result may be large, print it modulo 10⁹ + 7.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a directed graph, find the length of the smallest cycle in the graph.

A cycle in a graph is a path that starts and ends at the same vertex, passing through other vertices without repeating any edge. The length of a cycle is the number of the edges that form the cycle.

Your task is to determine the length of the smallest cycle present in the graph. If there are multiple cycles, you should identify the one with the least length. If the graph has no cycles, you should indicate that by returning -1 for that test case.

Input

The first line contains a number T (1 ≤ T ≤ 5), indicating the number of testcases.

For each test case:

• The first line contains two positive integers n and m, where 1 ≤ n ≤ 500 and 1 ≤ m ≤ 250000. These represent the number of vertices and edges in the graph.
• The vertices are numbered from 1 to n.
• The next m lines each contain two integers i, j (1 ≤ i, j ≤ n), describing a directed edge from vertex i to vertex j. 

Output

For each test case, output the length of the smallest cycle in the graph. If the graph has no cycles, output -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a connected graph G = (V, E) and a weight function w: E → N. Let H be a subgraph of G, we define the weight of H w(H) to be the sum of weight of all the edge in H. 

In this problem, you need to answer the weight of the second minimum spanning tree. Namely, let T₁ be a minimum spanning tree of G, find the weight of another spanning tree T₂ such that w(T₁) <= w(T₂) and w(T₂) <= w(T'), where T' is a spanning tree of G, T' ≠ T₁.

Input

There are two integer in the first line, n, m, which represent |V|, |E|.

In the following m lines, each line contains three integer: u, v, c, which is the endpoints of the edge and the weight of the edge respectivlely.

Constraint

• 3 <= n <= 1000
• n <= m <= min{2000, n x (n-1) / 2}
• In each line, 1 <= u, v <= n, u ≠ v
• 1 <= c <= 10⁹
• It is guaranteed that the answer exists.

Output

Output the answer in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss