{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eVocê recebe um grafo não-direcionado ponderado conectado, sem loops ou arestas múltiplas.\u003c/p\u003e\n\u003cp\u003eDeixe-nos lembrá-lo de que a \u003cspan class\u003d\"tex-font-style-underline\"\u003eárvore de cobertura\u003c/span\u003e de um grafo é definida como um subgrafo conectado acíclico do grafo fornecido que inclui todos os vértices do grafo. O \u003cspan class\u003d\"tex-font-style-underline\"\u003epeso\u003c/span\u003e de uma árvore é definido como a soma dos pesos das arestas que a árvore contém. A \u003cspan class\u003d\"tex-font-style-underline\"\u003eárvore de cobertura mínima\n\u003c/span\u003e (\u003cspan class\u003d\"tex-font-style-bf\"\u003eMST\u003c/span\u003e) de um grafo é definida como a árvore de cobertura do grafo com o menor peso possível. Para qualquer grafo conectado obviamente existe a árvore de cobertura mínima, mas no caso geral, a árvore de cobertura mínima de um grafo não é única.\u003c/p\u003e\n\u003cp\u003eSua tarefa é determinar o seguinte para cada aresta de um determinado grafo: se ela está incluída em \u003cspan class\u003d\"tex-font-style-bf\"\u003equalquer\u003c/span\u003e MST, ou incluída \u003cspan class\u003d\"tex-font-style-bf\"\u003eem pelo menos uma\u003c/span\u003e MST, ou \u003cspan class\u003d\"tex-font-style-bf\"\u003enão incluída em nenhuma\u003c/span\u003e MST.\u003c/p\u003e"}},{"title":"Entrada","value":{"format":"HTML","content":"\u003cp\u003eA primeira linha contém dois inteiros \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/97a78af0554f2de95e24a7be1c5885b5?v\u003d1696556002\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e) — o número de vértices e arestas do grafo, respectivamente. Em seguida, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e linhas, cada uma delas contendo três inteiros — a descrição das arestas do grafo como \"\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\" (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e, 1 ≤ \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e), onde \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e são os números de vértices conectados pela \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-ésima aresta, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e é o peso da aresta. É garantido que o grafo está conectado e não contém loops ou arestas múltiplas.\u003c/p\u003e"}},{"title":"Saída","value":{"format":"HTML","content":"\u003cp\u003eImprima \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e linhas — as respostas para todas as arestas. Se a \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-ésima aresta estiver incluída em qualquer MST, imprima \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eany\u003c/span\u003e\"; se a \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-ésima aresta estiver incluída em pelo menos uma MST, imprima \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eat least one\u003c/span\u003e\"; se a \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-ésima aresta não estiver incluída em nenhuma MST, imprima \"\u003cspan class\u003d\"tex-font-style-tt\"\u003enone\u003c/span\u003e\". Imprima as respostas para as arestas na ordem em que as arestas são especificadas na entrada.\u003c/p\u003e"}},{"title":"Exemplo 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSaída\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 5\n1 2 101\n1 3 100\n2 3 2\n2 4 2\n3 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003enone\nany\nat least one\nat least one\nany\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Exemplo 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSaída\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n1 2 1\n2 3 1\n1 3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eany\nany\nnone\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Exemplo 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSaída\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n1 2 1\n2 3 1\n1 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eat least one\nat least one\nat least one\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Observações","value":{"format":"HTML","content":"\u003cp\u003eNo exemplo 2, a MST é única para o grafo dado: ela contém as duas primeiras arestas.\u003c/p\u003e\n\u003cp\u003eNo exemplo 3, quaisquer duas arestas formam a MST para o grafo fornecido. Isso significa que cada aresta está incluída em pelo menos uma MST.\u003c/p\u003e"}}]}