{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eYou are given an integer \u003cvar\u003e\\(L\\)\u003c/var\u003e. Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eThe number of vertices, \u003cvar\u003e\\(N\\)\u003c/var\u003e, is at most \u003cvar\u003e\\(20\\)\u003c/var\u003e. The vertices are given ID numbers from \u003cvar\u003e\\(1\\)\u003c/var\u003e to \u003cvar\u003e\\(N\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eThe number of edges, \u003cvar\u003e\\(M\\)\u003c/var\u003e, is at most \u003cvar\u003e\\(60\\)\u003c/var\u003e. Each edge has an integer length between \u003cvar\u003e\\(0\\)\u003c/var\u003e and \u003cvar\u003e\\(10^6\\)\u003c/var\u003e (inclusive).\u003c/li\u003e\r\n\u003cli\u003eEvery edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, \u003cvar\u003e\\(1,2,...,N\\)\u003c/var\u003e is one possible topological order of the vertices.\u003c/li\u003e\r\n\u003cli\u003eThere are exactly \u003cvar\u003e\\(L\\)\u003c/var\u003e different paths from Vertex \u003cvar\u003e\\(1\\)\u003c/var\u003e to Vertex \u003cvar\u003e\\(N\\)\u003c/var\u003e. The lengths of these paths are all different, and they are integers between \u003cvar\u003e\\(0\\)\u003c/var\u003e and \u003cvar\u003e\\(L-1\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eHere, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(2 \\leq L \\leq 10^6\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(L\\)\u003c/var\u003e is an integer.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(L\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eIn the first line, print \u003cvar\u003e\\(N\\)\u003c/var\u003e and \u003cvar\u003e\\(M\\)\u003c/var\u003e, the number of the vertices and edges in your graph.\r\nIn the \u003cvar\u003e\\(i\\)\u003c/var\u003e-th of the following \u003cvar\u003e\\(M\\)\u003c/var\u003e lines, print three integers \u003cvar\u003e\\(u_i,v_i\\)\u003c/var\u003e and \u003cvar\u003e\\(w_i\\)\u003c/var\u003e, representing the starting vertex, the ending vertex and the length of the \u003cvar\u003e\\(i\\)\u003c/var\u003e-th edge.\r\nIf there are multiple solutions, any of them will be accepted.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","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\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8 10\r\n1 2 0\r\n2 3 0\r\n3 4 0\r\n1 5 0\r\n2 6 0\r\n3 7 0\r\n4 8 0\r\n5 6 1\r\n6 7 1\r\n7 8 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003eIn the graph represented by the sample output, there are four paths from Vertex \u003cvar\u003e\\(1\\)\u003c/var\u003e to \u003cvar\u003e\\(N\u003d8\\)\u003c/var\u003e:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e → \u003cvar\u003e\\(2\\)\u003c/var\u003e → \u003cvar\u003e\\(3\\)\u003c/var\u003e → \u003cvar\u003e\\(4\\)\u003c/var\u003e → \u003cvar\u003e\\(8\\)\u003c/var\u003e with length \u003cvar\u003e\\(0\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e → \u003cvar\u003e\\(2\\)\u003c/var\u003e → \u003cvar\u003e\\(3\\)\u003c/var\u003e → \u003cvar\u003e\\(7\\)\u003c/var\u003e → \u003cvar\u003e\\(8\\)\u003c/var\u003e with length \u003cvar\u003e\\(1\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e → \u003cvar\u003e\\(2\\)\u003c/var\u003e → \u003cvar\u003e\\(6\\)\u003c/var\u003e → \u003cvar\u003e\\(7\\)\u003c/var\u003e → \u003cvar\u003e\\(8\\)\u003c/var\u003e with length \u003cvar\u003e\\(2\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e → \u003cvar\u003e\\(5\\)\u003c/var\u003e → \u003cvar\u003e\\(6\\)\u003c/var\u003e → \u003cvar\u003e\\(7\\)\u003c/var\u003e → \u003cvar\u003e\\(8\\)\u003c/var\u003e with length \u003cvar\u003e\\(3\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eThere are other possible solutions.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","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\u003e5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5 7\r\n1 2 0\r\n2 3 1\r\n3 4 0\r\n4 5 0\r\n2 4 0\r\n1 3 3\r\n3 5 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}