// 2023.04.15 at 23:24:31 HKT import java.io.BufferedInputStream import java.io.File import java.io.PrintWriter import kotlin.system.measureTimeMillis import java.util.TreeMap import java.util.TreeSet import kotlin.random.Random import kotlin.random.nextInt // 1. Modded const val p = 1000000007L const val pI = p.toInt() fun Int.adjust():Int{ if(this >= pI){ return this - pI }else if (this < 0){ return this + pI };return this } fun Int.snap():Int{ if(this >= pI){return this - pI} else return this} infix fun Int.mm(b:Int):Int{ return ((this.toLong() * b) % pI).toInt() } infix fun Int.mp(b:Int):Int{ val ans = this + b;return if(ans >= pI) ans - pI else ans } infix fun Int.ms(b:Int):Int{ val ans = this - b;return if(ans < 0) ans + pI else ans } fun Int.inverse():Int = intPow(this,pI-2,pI) infix fun Int.modDivide(b:Int):Int{ return this mm (b.inverse()) } fun intPow(x:Int,e:Int,m:Int):Int{ var X = x ; var E =e ; var Y = 1 while(E > 0){ if(E and 1 == 0){ X = ((1L * X * X) % m).toInt() E = E shr 1 }else{ Y = ((1L * X * Y) % m).toInt() E -= 1 } } return Y } // 2. DP initial values const val plarge = 1_000_000_727 const val nlarge = -plarge const val phuge = 2_727_000_000_000_000_000L const val nhuge = -phuge // 3. convenience conversions val Boolean.chi:Int get() = if(this) 1 else 0 //characteristic function val BooleanArray.chiarray:IntArray get() = IntArray(this.size){this[it].chi} val Char.code :Int get() = this.toInt() - 'a'.toInt() //3. hard to write stuff fun IntArray.put(i:Int,v:Int){ this[i] = (this[i] + v).adjust() } val mint:MutableList get() = mutableListOf() val mong:MutableList get() = mutableListOf() val mchar:MutableList get() = mutableListOf() //4. more outputs fun List.conca():String = this.joinToString("") val CharArray.conca :String get() = this.joinToString("") val IntArray.conca :String get() = this.joinToString(" ") @JvmName("concaInt") fun List.conca():String = this.joinToString(" ") val LongArray.conca:String get() = this.joinToString(" ") @JvmName("concaLong") fun List.conca():String = this.joinToString(" ") //5. Pair of ints const val longmask = (1L shl 32) - 1 fun makepair(a:Int, b:Int):Long = (a.toLong() shl 32) xor (longmask and b.toLong()) val Long.first get() = (this ushr 32).toInt() val Long.second get() = this.toInt() //6. strings val String.size get() = this.length const val randCount = 100 //7. bits fun Int.has(i:Int):Boolean = (this and (1 shl i) != 0) fun Long.has(i:Int):Boolean = (this and (1L shl i) != 0L) //8 TIME inline fun TIME(f:()->Unit){ val t = measureTimeMillis(){ f() } println("$t ms") } //9.ordered pair fun order(a:Int, b:Int):Pair{ return Pair(minOf(a,b), maxOf(a,b)) } //10 rand fun rand(x:Int) = Random.nextInt(x) fun rand(x:IntRange) = Random.nextInt(x) val coin:Boolean get() = Random.nextBoolean() //11 typing issues, rename typealias ints = IntArray typealias longs = LongArray typealias bools = BooleanArray typealias pii = Pair const val interactive = true object Reader{ private const val BS = 1 shl 16 private const val NC = 0.toChar() private val buf = ByteArray(BS) private var bId = 0 private var size = 0 private var c = NC var warningActive = true var fakein = StringBuilder() private var IN: BufferedInputStream = BufferedInputStream(System.`in`, BS) val OUT: PrintWriter = PrintWriter(System.out) private val char: Char get() { if(interactive){ return System.`in`.read().toChar() } while (bId == size) { size = IN.read(buf) // no need for checked exceptions if (size == -1) return NC bId = 0 } return buf[bId++].toChar() } fun nextInt(): Int { var neg = false if (c == NC) c = char while (c < '0' || c > '9') { if (c == '-') neg = true c = char } var res = 0 while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0') c = char } return if (neg) -res else res } fun nextLong(): Long { var neg = false if (c == NC) c = char while (c < '0' || c > '9') { if (c == '-') neg = true c = char } var res = 0L while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0') c = char } return if (neg) -res else res } fun nextString():String{ val ret = StringBuilder() while (true){ c = char if(!isWhitespace(c)){ break} } ret.append(c) while (true){ c = char if(isWhitespace(c)){ break} ret.append(c) } return ret.toString() } fun isWhitespace(c:Char):Boolean{ return c == ' ' || c == '\n' || c == '\r' || c == '\t' } fun rerouteInput(){ if(warningActive){ put("Custom test enabled") println("Custom test enabled") warningActive = false } val S = fakein.toString() println("New Case ") println(S.take(80)) println("...") fakein.clear() IN = BufferedInputStream(S.byteInputStream(),BS) } fun flush(){ OUT.flush() } fun takeFile(name:String){ IN = BufferedInputStream(File(name).inputStream(),BS) } } fun eat(){ val st1 = TreeSet(); val st2 = TreeMap()} fun put(aa:Any){ Reader.OUT.println(aa) // if(interactive){ Reader.flush()} } fun put(vararg x:Any){ for(c in x){ Reader.OUT.print(c) Reader.OUT.print(" ") } Reader.OUT.print("\n") if(interactive){ Reader.flush()} } fun done(){ Reader.OUT.close() } fun share(aa:Any){ Reader.fakein.append(format(aa)) Reader.fakein.append("\n") } val getintfast:Int get() = Reader.nextInt() val getint:Int get(){ val ans = getlong ; if(ans > Int.MAX_VALUE) IntArray(1000000000); return ans.toInt() } val getlong:Long get() = Reader.nextLong() val getstr:String get() = Reader.nextString() fun getline(n:Int):IntArray{ return IntArray(n){getint} } fun getlineL(n:Int):LongArray{ return LongArray(n){getlong} } fun subformat(a:Any?):String{ // for not a collection return if(a == null) "null" else if(a is Iterable<*> ) a.joinToString(" ") else if(a is BooleanArray) a.joinToString("") { if (it) "1" else "0" } else if(a is IntArray) a.joinToString(" ") else if(a is LongArray) a.joinToString(" ") else a.toString() } fun format(a:Any?):String { if (a == null) { return "null" } else if (a is BooleanArray) { return a.joinToString("") { if (it) "1" else "0" } } else if (a is Array<*>) { return "\n"+a.joinToString("\n"){subformat(it)} } else { return subformat(a)} } var dmark = -1 infix fun Any.dei(a:Any?){ dmark++ ; debug() println("<${dmark}> ${this} : ${format(a)}") } const val just = " " fun crash(){ throw Exception("Bad programme")} fun assert(a:Boolean){ if(!a){ throw Exception("Failed Assertion") }} enum class solveMode { real, rand, tc } object solve{ var mode:solveMode = solveMode.real var tcNum:Int = 0 var rand:()->Unit = {} var TC:MutableMapUnit> = mutableMapOf() var tn:Long = 0 fun cases(onecase:()->Unit){ val t = if(mode == solveMode.real){if(singleCase) 1 else getint} else if(mode == solveMode.tc){1 } else randCount if(pI != 998_244_353 && pI != 1_000_000_007){ throw Exception("Not usual primes!") } if(t == 1 && mode != solveMode.real){ tn = System.currentTimeMillis() } repeat(t){ if(mode == solveMode.tc){ TC[tcNum]?.let { it() } Reader.rerouteInput() }else if(mode == solveMode.rand){ rand() Reader.rerouteInput() } onecase() } if(t == 1 && mode != solveMode.real){ val dt = System.currentTimeMillis() - tn println("Time $dt ms ") } } fun rand(a:()->Unit){ this.rand = a } fun tc(id:Int = 0,a:()->Unit){ TC[id] = a } fun usetc(a:Int = 0 ){ this.tcNum = a this.mode = solveMode.tc } fun userand(){ this.mode = solveMode.rand } } fun debug(){} fun Int.previous(mod:Int): Int { return if(this == 0) mod - 1 else this - 1 } fun Int.next(mod:Int): Int{ return (if(this == mod-1) 0 else this + 1) } fun Int.modnegate(mod:Int):Int{ return if(this == 0) 0 else mod-this } fun Int.lightadjust(mod:Int):Int{ return if(this < 0) this + mod else if(this >= mod) this - mod else this } fun Int.lightminus(other:Int,mod:Int):Int{ val now = this - other if(now < 0){ return now + mod }else{ return now } } fun Int.distanceTo(other:Int, mod:Int):Int{ if(this <= other){ return other - this }else{ return other - this + mod } } private typealias ei = Int private typealias earr = IntArray //NOT batle tested class fastDeque(val l:Int, val r:Int) { val total = r - l + 1 val st = earr(total) var startpointer = 0 - l var endpointer = startpointer - 1 val size: Int get() = endpointer - startpointer + 1 val lastIndex:Int get() = endpointer fun reset(){ startpointer = -l endpointer = startpointer -1 } fun isEmpty(): Boolean { return endpointer < startpointer } fun isNotEmpty():Boolean{ return endpointer >= startpointer } fun first():ei{ assert(isNotEmpty()) return st[startpointer] } fun last():ei{ assert(isNotEmpty()) return st[endpointer] } fun addFirst(v:ei ){ startpointer -- st[startpointer]= v } fun addLast(v:ei){ endpointer ++ st[endpointer] = v } fun removeFirst(): ei { assert(isNotEmpty()) val ret = st[startpointer] startpointer ++ return ret } fun removeLast(): ei { assert(isNotEmpty()) val ret = st[endpointer] endpointer -- return ret } fun toArray():earr{ return st.sliceArray(startpointer..endpointer) } fun toList():List{ return st.slice(startpointer..endpointer) } inline fun forEach(act:(v:ei)->Unit){ for(i in startpointer..endpointer){ act(st[i]) } } inline fun withIndex(act:(i:Int,v:ei)->Unit){ for(i in startpointer..endpointer){ act(i-startpointer,st[i]) } } operator fun get(v:Int): ei { return st[startpointer + v] } } fun fastEmptyList(max:Int):fastDeque{ return fastDeque(0,max-1) } const val graphWeighed = false class Graph(val n:Int, val m:Int, val directed:Boolean) { val maxedge = if (directed) m else m * 2 var cnt = -1 val edgecount:Int get() = cnt + 1 val next = IntArray(maxedge) val head = IntArray(n) { -1 } val to = IntArray(maxedge) val from = IntArray(maxedge) val weights = IntArray(if (graphWeighed) m else 0) val Q = fastDeque(0,n) private fun primitive_add(u: Int, v: Int): Int { next[++cnt] = head[u] head[u] = cnt to[cnt] = v from[cnt] = u return cnt } fun add(u: Int, v: Int): Int { val e = primitive_add(u, v) if (!directed) { primitive_add(v, u) } return if (directed) e else e shr 1 } fun addWeighted(u: Int, v: Int, w: Int):Int{ val e = add(u, v) weights[e] = w return e } //Basic Transversals inline fun NS(a:Int, act:(Int)->Unit){ var i= head[a] while(i != -1){ act(to[i]) i = next[i] } } inline fun NS_E(a:Int, act:(e:Int,v:Int)->Unit){ var i= head[a] while(i != -1){ act(i,to[i]) i = next[i] } } inline fun everyEdge(act:(a:Int, b:Int)->Unit){ val s = if(directed) 1 else 2 for(e in 0 until edgecount step s ){ act(from[e], to[e]) } } inline fun everyDirectedEdge(act:(a:Int, b:Int)->Unit){ for(e in 0 until edgecount){ act(from[e], to[e]) } } // Store a spanning tree, var root = 0 var preorder:IntArray = IntArray(0) var parent:IntArray = IntArray(0) val hasDFSorder:Boolean get() = preorder.size == n var parentEdge:IntArray = IntArray(0) //stores the order fun treeOrderDFS(withEdges:Boolean = false){ parent = IntArray(n){-1} var pt = -1 preorder = IntArray(n){-1} if(withEdges) parentEdge = IntArray(n){-1} Q.reset() // val Q = fastDeque(0,n) parent[root] = root Q.addLast(root) while(Q.isNotEmpty()){ val a = Q.removeLast() val p = parent[a] preorder[++pt] = a NS_E(a){e,v -> if(v == p) return@NS_E if(withEdges) parentEdge[v] = if(directed) e else (e shr 1) parent[v] = a Q.addLast(v) } } } inline fun BFS(distRoot:Int, reached:(Int, Int)->Unit = {_,_ ->}): IntArray { Q.reset() val explored = IntArray(n+1){-1} // also store parents Q.addLast(distRoot) explored[distRoot] = -2 val dist = IntArray(n){-1} dist[distRoot] = 0 while(Q.size > 0){ val x = Q.removeFirst() reached(x,explored[x]) NS(x){ a-> if(explored[a] == -1){ explored[a] = x dist[a] = dist[x] + 1 Q.addLast(a) } } } return dist } inline fun trueOrderDFS(root:Int?,newroot:(r:Int) ->Unit, preexplore:(v:Int) ->Unit, postExplore:(v:Int)->Unit, move:(p:Int,v:Int,e:Int)->Unit, cross:(from:Int, to:Int,e:Int)->Unit ){ Q.reset() val explored = BooleanArray(n){false} val headHere = head.copyOf() for(i in 0 until n) { if (explored[i] || (root != null && root != i)) continue newroot(i) explored[i] = true Q.addLast(i) while(Q.isNotEmpty()){ val v = Q.last() val e = headHere[v] if(e == head[v]){ preexplore(v) } if(e == -1){ postExplore(v) Q.removeLast() continue } headHere[v] = next[e] val t = to[e] if(!explored[t]){ explored[t] = true move(v,t,e) Q.addLast(t) }else{ cross(v,t,e) } } } } fun EulerDoubleOrder(): Pair { var pointer = -1 val euler = IntArray(2 * n - 1) val entry = IntArray(n) fun dfs(v:Int, p:Int) { euler[++pointer] = v entry[v] = pointer NS(v){ w-> if(w == p) return@NS dfs(w,v) euler[++pointer] = v } } dfs(root,-1) return Pair(euler, entry) } //Tree Transversals inline fun leafFirst(act:(Int)->Unit){ if(!hasDFSorder) treeOrderDFS() for(i in preorder.lastIndex downTo 0){ act(preorder[i]) } } inline fun rootFirst(act:(Int)->Unit){ if(!hasDFSorder) treeOrderDFS() for(a in preorder){ act(a) } } inline fun rootFirstEdge(act:(from:Int, to:Int, e:Int)->Unit){ if(!hasDFSorder) treeOrderDFS(true) for(i in 1 until preorder.size){ val v = preorder[i] act(parent[v],v,parentEdge[v]) } } // Basic invariants maintaining fun calculateParents():IntArray{ if(!hasDFSorder) treeOrderDFS() return parent } fun calculateSizes():IntArray{ val ret = IntArray(n){1} leafFirst { v -> if(v != root) ret[parent[v]] += ret[v] } return ret } fun calculateSubtreeSum(weights:IntArray){ leafFirst { v -> if(v != root) weights[parent[v]] += weights[v] } } fun calculateDepth(): IntArray { val ret = IntArray(n) rootFirst { v -> if(v != root) ret[v] = ret[parent[v]] + 1 } return ret } inline fun subs(v:Int, act:(Int)->Unit){ NS(v){w -> if(w != parent[v]) act(w) } } fun calculateDepthWeighted(): LongArray { val ret = LongArray(n) rootFirstEdge{from,to,e -> ret[to] = ret[from] + weights[e]} return ret } fun outdegree():IntArray{ val ret = IntArray(n) everyDirectedEdge { a, b -> ret[a] ++ } return ret } fun indegree():IntArray{ val ret = IntArray(n) everyDirectedEdge {a, b -> ret[b] ++} return ret } fun degree():IntArray = outdegree() fun reversed():Graph{ assert(directed) val new = Graph(n,m,true) everyDirectedEdge { a, b -> new.add(b,a) } return new } fun intime():IntArray{ val tin = IntArray(n) if(!hasDFSorder) treeOrderDFS() for(i in 0 until n) tin[preorder[i]] = i return tin } fun outtime():IntArray{ val tout = intime() leafFirst { v -> val p = parent[v] if(p == v) return@leafFirst tout[p] = maxOf(tout[p], tout[v]) } return tout } fun markcomponent():IntArray{ val ret = IntArray(n) rootFirst { v -> if(v == root) return@rootFirst if(parent[v] == root){ ret[v] = v; return@rootFirst} ret[v] = ret[parent[v]] } return ret } } fun findpath(edgelist:List):List{ val present = TreeSet() for((a,b) in edgelist){ present.add(a) present.add(b) } val n = present.last() + 1 val G = Graph(n,n-1,false) for((a,b) in edgelist){ G.add(a,b) } val x = present.first() val d1 = G.BFS(x) val root2 = (0 until n).maxByOrNull { d1[it] }!! val d2 = G.BFS(root2) val final = present.sortedBy { d2[it] } return final } fun findcycle(edgelist:List):List{ return findpath(edgelist.drop(1)) } const val live = true const val singleCase = false fun main(){ // solve.userand() solve.cases{ // val n = 4 // val l = 5 // val n = getint // val l = getint val n = if(live) getint else (rand(7)+3) var l = if(live) getint else Random.nextInt(n..(n * (n-1)/2)) val go = mutableSetOf() for(i in 0 until n){ val next = i.next(n) val (a,b) = order(i,next) go.add(a to b ) } outer@for(i in 0 until n){ for(j in i+1 until n){ if(go.size == l) break@outer go.add(i to j) } } for((a,b) in go){ put("${a+1} ${b+1}") } Reader.flush() val receive = mutableListOf() if(live) { repeat(l) { receive.add((getint - 1) to (getint - 1)) } }else{ val perm = (0 until n).shuffled() for((a,b) in go){ receive.add(order(perm[a],perm[b])) } } val degree = ints(n) for((a,b) in receive){ degree[a] ++ degree[b] ++ } val isfull = bools(n) val full = mint for(i in 0 until n){ if(degree[i] == n-1){ full.add(i) isfull[i] = true } } val useful = receive.filter { !isfull[it.first] && !isfull[it.second] } val have = useful.toSet() val remain = n- full.size val final:List if(useful.isEmpty()){ if(full.size == n){ final = listOf() }else{ assert(full.size == n-2) val S = full.toSet() val remain = (0 until n).filter { it !in S } val (a,b) = remain assert(full.size >= 2 ) final = listOf(a) + full[0] + listOf(b) + full.takeLast(full.size -1) full.clear() } } else if(useful.size == remain -1){ final = findpath(useful) }else if(useful.size == remain){ final = findcycle(useful) }else if(useful.size == remain + 1 ){ val degree = ints(n) for((a,b) in useful){ degree[a] ++ degree[b] ++ } val three = (0 until n).filter { degree[it] == 3 } val (a,b) = order(three[0],three[1]) val new = useful.filter { it != (a to b) } final = findcycle(new) }else{ val degree = ints(n) for((a,b) in useful){ degree[a] ++ degree[b] ++ } val key = (0 until n).maxByOrNull { degree[it] }!! val new = useful.filter { it.first != key && it.second != key } val p = findpath(new) if(order(key,p[0]) in have){ final = listOf(key) + p }else{ final = p + listOf(key) } } val out = (final + full) // val startset = receive.toSet() // assert(out.size == n) // for(i in 0 until n){ // assert(order(out[i], out[i.next(n)]) in startset) // } put((out).map { it+1 }.conca()) Reader.flush() } done() } /* 1 4 5 1 2 2 3 3 4 1 4 1 3 */