Dr. Prakash recently learned about how the human brain evolved a marvelous ability to form, prune, and reshape connections between neurons. (He should have learned this awhile ago in medical school, but Dr. Prakash isn't the best medical student, or medical doctor for that matter.)
He would like to test this himself by performing some basic neurectomies on his victim patient and observing the results. He did receive consent to do this (like many of us, his patient did not read all the fine print before signing), but the medical board is still very much on his case due to the outcomes of his previous patients. As such, Dr. Prakash wants to avoid killing his patient (again), which happens if part of the brain becomes totally disconnected and unable to communicate with another part of the brain (a full lobotomy).
Dr. Prakash will make a single cut. Please help him identify which neurons he should definitely avoid with this cut if he wishes to keep his medical license (at least until the next ethics hearing).
The first line contains $$$n$$$ $$$(2 \leq n \leq m + 1)$$$ and $$$m$$$ $$$(1 \leq m \leq 2 * 10^5)$$$, the number of neurons representing the patient's brain, and the number of connections/synapses between neurons.
The next $$$m$$$ lines contain $$$i_m$$$ $$$(0 \leq i_m \lt 2^{32})$$$, a unique integer identifier for the synapse, and $$$n_1$$$ and $$$n_2$$$ $$$(0 \leq n_1, n_2 \lt n)$$$, denoting the two neurons that are connected. Please note that a pair of neurons may be connected by multiple synapses, and that $$$n1$$$ may equal $$$n2$$$.
It is guaranteed that the brain is connected at the start.
Print a single line of a sorted list of synapse identifiers that, if cut, will cause a brain partition. If there are none, print -1.
4 4212 3 0238 1 2394 2 0281 0 1
212
3 3101 0 1102 0 2103 2 1
-1
