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 Input Output 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
edge 1-2, 2-3 with 1 red edge edge 1-2, 1-3 with 1 red edge 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.
connect edge 1-2, 2-4, 4-5 ,4-3 with 3 red edges connect edge 1-5, 5-4, 4-2, 2-3 with 2 red edges 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.
Can you give a link to the problem? Otherwise seems interesting!
Ok, it has been sufficient time now, I think it is safe to answer. Besides, I think this solution is pretty cool.
First, recall that we can calculate the spanning tree with minimum number of red edges as well as the spanning tree with maximum number of red edges with any MST algorithm you like. Let's denote the trees $$$T_L$$$ and $$$T_R$$$ respectively, and the number of red edges in those trees as $$$L$$$ and $$$R$$$.
Suppose we have any tree $$$T$$$ that is different from $$$T_L$$$. There must be an edge $$$e$$$ that exists in $$$T_L$$$ but not in $$$T$$$. Let's add that edge to $$$T$$$. Now $$$T$$$ contains a cycle, which must contain an edge $$$e'$$$ not present in $$$T_L$$$. Remove $$$e'$$$ from $$$T$$$, now $$$T$$$ is a tree again. After this operation, the number of red edges has changed by at most one (it may have increased, decreased or stayed the same).
If we start this process at $$$T_R$$$ and repeat the steps until we have $$$T_L$$$, we must have visited a tree with $$$i$$$ red edges for all $$$L \leqslant i \leqslant R$$$.