5 6 1 2 6 2 3 4 1 3 5 2 4 3 4 5 2 3 5 1
15 By painting edges $2,3,4,5$, and $6$, * edges $2,4,5$, and $6$ forms a simple cycle, and * edge $3$ connects vertex $3$ (on the cycle) and vertex $1$ (not on the cycle), so one can make a Q with a total cost of $4+5+3+2+1=15$. Making a Q in another way costs $15$ or greater, so the answer is $15$.
4 4 1 2 1 2 3 1 3 4 1 1 4 1
\-1
6 15 2 6 48772 2 4 36426 1 6 94325 3 6 3497 2 3 60522 4 5 63982 4 6 4784 1 2 14575 5 6 68417 1 5 7775 3 4 33447 3 5 90629 1 4 47202 1 3 90081 2 5 79445
78154
{
"problem": {
"name": "Ex - Make Q",
"description": {
"content": "There is a simple undirected graph with $N$ vertices and $M$ edges. The edges are initially painted white. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $",
"description_type": "Markdown"
},
"platform": "AtCoder",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "abc308_h"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There is a simple undirected graph with $N$ vertices and $M$ edges. The edges are initially painted white. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $...",
"is_translate": false,
"language": "English"
}
]
}