{"trustable":true,"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eEven though he isn\u0027t a student of computer science, Por Costel the pig has started to study Graph Theory. Today he\u0027s learning about Bellman-Ford, an algorithm that calculates the minimum cost path from a source node (for instance, node 1) to all the other nodes in a directed graph with weighted edges. Por Costel, utilizing his scarce programming knowledge has managed to scramble the following code in C++, a variation of the Bellman-Ford algorithm:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/a091b360ac4205c63030dd4992a842a5?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eYou can notice a lot of deficiencies in the above code. In addition to its rudimentary documentation, we can see that Por Costel has stored this graph as an array of edges (the array \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/a88bff0abf5d860c7d42d6a05dfad71f?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e). An edge is stored as the triplet \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/51dedeb6839c0e019b6dde1b9b714a1f?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e signifying an edge that spans from \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/ff1a1b9a805648d7dc3a6de1ab04b018?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e to \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/478cee1e9f4ee5113b72eab0034341ac?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e and has weight \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/567885ab47e7fe793d699ae8032af2ae?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. But even worse is the fact that the algorithm is SLOW!\u003c/p\u003e\u003cp\u003eAs we want our hooved friend to walk away with a good impression about computer science, we want his code to execute as FAST as possible. In order to do so, we can modify the order of edges in the array \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/a88bff0abf5d860c7d42d6a05dfad71f?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e so that the while loop executes a small number of times.\u003c/p\u003e\u003cp\u003eGiven a directed graph of \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/d67a84d7273a1bbe633735650a457d73?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e nodes and \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/38aabe3ad657ad695c7df4a2b4f95e33?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e edges, you are asked to produce an ordering of the edges such that the Bellman-Ford algorithm written by Por Costel should finish after at most two iterations of the while loop(that is, the program should enter the while loop at most twice).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the file \u003cspan class\u003d\"tex-font-style-bf\"\u003ealgoritm.in\u003c/span\u003e will contain an integer \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/5442cc79ebe2de5a716226d6108b71d9?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/fc1b66c12840908f8446525348c936d3?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, the number of test cases.\u003c/p\u003e\u003cp\u003eEach of the \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/5442cc79ebe2de5a716226d6108b71d9?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e test cases has the following format: on the first line, there are two numbers \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/d67a84d7273a1bbe633735650a457d73?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e and \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/38aabe3ad657ad695c7df4a2b4f95e33?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/1edd2656e8f4719e7f1f154d4f1df528?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e), the number of nodes and the number of edges in the graph respectively. \u003c/p\u003e\u003cp\u003eThe next \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/38aabe3ad657ad695c7df4a2b4f95e33?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e lines describe the edges, each containing three integers \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/57cdb32e2b61fb79d3e044bcb6e08dc4?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e signifying there is an edge from node \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/ff1a1b9a805648d7dc3a6de1ab04b018?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e to node \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/478cee1e9f4ee5113b72eab0034341ac?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e with weight \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/567885ab47e7fe793d699ae8032af2ae?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/7116417c866ab0903bf496aac38e5a5e?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e)\u003c/p\u003e\u003cp\u003eIt is guaranteed that node \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9e565016574bb04eb367059c2f433e9d?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e has at least one outgoing edge.\u003c/p\u003e\u003cp\u003eThe graph may contain self loops and/or multiple edges.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output file \u003cspan class\u003d\"tex-font-style-bf\"\u003ealgoritm.out\u003c/span\u003e should contain \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/5442cc79ebe2de5a716226d6108b71d9?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e lines representing the answers to each test case.\u003c/p\u003e\u003cp\u003eFor each test case you should output a permutation of numbers from \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9e565016574bb04eb367059c2f433e9d?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e to \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/38aabe3ad657ad695c7df4a2b4f95e33?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, representing the order of the edges you want in Por Costel\u0027s array of edges \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/a88bff0abf5d860c7d42d6a05dfad71f?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. \u003c/p\u003e\u003cp\u003eThe edges are considered indexed by the order in which they are given in the input (the \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/55138592ef6590705e99ae692a4c0c23?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e-th edge read is the edge with index \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/55138592ef6590705e99ae692a4c0c23?v\u003d1714924793\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e).\u003c/p\u003e\u003cp\u003eIf there are multiple solutions, you are allowed to print any of them.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4 4\n1 2 1\n3 4 2\n2 3 3\n1 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4 2 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}