Sonal And Forests
All submissions for this problem are available.
Sonal is an avid nature lover and also has a knack for programming. Since today's her birthday, her teacher gave her a problem on spanning forests.
A spanning forest is a subgraph of a weighted graph such that every two vertices in the same connected component in the weighted graph are also in the same connected component in the subgraph. Also, there are no cycle or loops in a spanning forest.
A spanning forest with minimum sum of edge weights is called minimum spanning forest.
A spanning forest with maximum sum of edge weights is called maximum spanning forest.
Now, she has N vertices and M weighted edges. Edges are numbered from 1 to M and are added to the graph accordingly.
She now wants to find the minimum possible edge number such that she has different minimum and maximum spanning forests at that time after adding that edge.
First line consists of two numbers N and M denoting the number of vertices and the number of weighted edges respectively.
Next M lines consists of three numbers u, v and w denoting that vertices u and v are connected by an edge whose weight is w.
Print the edge number for each test case in a new line. If she won't get a minimum and maximum spanning forest even after adding all the M edges, then print "-1" without the quotes.
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 105
- 1 ≤ u ≤ v ≤ 105
Input 1: 3 2 1 2 3 2 3 5 Output 1: -1
Input 2: 3 3 1 2 3 2 3 5 3 1 2 Output 2: 3
In first case Sonal won't get different minimum and maximum forests even after adding all the edges. So, the answer is -1.
In second case Sonal gets different minimum and maximum spanning forests after adding the third edge. So, answer is 3.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions