Limits 1s, 512 MB

You are given a bidirectional graph with N vertices and M edges. All edges are painted into either red or black. Your job is to find a spanning tree with some prime number of red edges.

Input

First line contains the number of test cases T(1≤ T ≤10).

For each test case:

First line consists of two integers denoting N(1≤ N ≤100000) and M(0≤ M ≤200000).

Next M lines consist of two integers A, B and C denoting there is a directed road from A to B (1≤ A,B ≤N) with color C(0 for black and 1 for red).The graph may contain self loops and multiple edges between two nodes.

Output

For every test case, you need to print “Case T: ” (where T is the test case number) followed by the prime number. If you can not construct such a tree print -1.
If you can use multiple prime, print the largest one.

Sample

InputOutput
3
3 3
1 2 0
2 3 1
1 3 1
5 6
1 2 1
2 3 0
3 4 1
1 5 1
5 4 0
2 4 1
5 4
1 2 1
1 3 1
1 4 1
1 5 1
Case 1: 2
Case 2: 3
Case 3: -1

Test Case 1:
You can make a spanning tree by connecting

  1. edge 1-2, 2-3 with 1 red edge
  2. edge 1-2, 1-3 with 1 red edge
  3. edge 1-2, 2-3 with 2 red edges
    as 2 is the largest prime that can be used to construct a spanning tree, the answer is 1.

Test Case 2:
You can make a spanning tree in several ways. I'll describe three of them below.

  1. connect edge 1-2, 2-4, 4-5 ,4-3 with 3 red edges
  2. connect edge 1-5, 5-4, 4-2, 2-3 with 2 red edges
  3. connect edge 1-5, 1-2, 2-4, 4-3 with 4 red edges
    as 4 is not a prime and 3 is larger between 2 and 3, the answer is 3.

Test Case 3:
The only way you can make a spanning tree is using 4 red edges. But 4 is not a prime. Hence the answer is -1.

Submit

Login to submit.

Statistics

67% Solution Ratio
saiful.dhEarliest, Apr '21
steinumFastest, 0.0s
steinumLightest, 5.5 kB
steinumShortest, 1898B
Toph uses cookies. By continuing you agree to our Cookie Policy.