fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    val edges = Array(N + 1) { mutableListOf<Int>() }

    repeat(N - 1) {
        val (a, b) = readInputLine().split(" ").map { it.toInt() }
        edges[a].add(b)
        edges[b].add(a)
    }

    val redNodes = mutableListOf<Int>()
    val blueNodes = mutableListOf<Int>()

    fun dfs(isRed: Boolean, node: Int, parent: Int) {
        if (isRed) {
            redNodes.add(node)
        } else {
            blueNodes.add(node)
        }

        for (e in edges[node]) {
            if (e == parent) {
                continue
            }
            dfs(!isRed, e, node)
        }
    }

    dfs(false, 1, 0)

    val ans = IntArray(N)

    when {
        redNodes.size > N / 3 && blueNodes.size > N / 3 -> {
            var oneNodeCnt = 0
            var twoNodeCnt = 0
            var threeNodeCnt = 0
            for (r in redNodes) {
                if (oneNodeCnt * 3 < N) {
                    ans[r - 1] = oneNodeCnt++ * 3 + 1
                } else {
                    ans[r - 1] = ++threeNodeCnt * 3
                }
            }
            for (b in blueNodes) {
                if (twoNodeCnt * 3 + 1 < N) {
                    ans[b - 1] = twoNodeCnt++ * 3 + 2
                } else {
                    ans[b - 1] = ++threeNodeCnt * 3
                }
            }
        }
        redNodes.size <= N / 3 -> {
            var threeNodeCnt = 0
            var otherNodeCnt = 0
            for (r in redNodes) {
                ans[r - 1] = ++threeNodeCnt * 3
            }
            for (b in blueNodes) {
                if (threeNodeCnt * 3 + 2 < N) {
                    ans[b - 1] = ++threeNodeCnt * 3
                } else {
                    ans[b - 1] = otherNodeCnt / 2 * 3 + otherNodeCnt % 2 + 1
                    otherNodeCnt++
                }
            }
        }
        else -> {
            var threeNodeCnt = 0
            var otherNodeCnt = 0
            for (b in blueNodes) {
                ans[b - 1] = ++threeNodeCnt * 3
            }
            for (r in redNodes) {
                if (threeNodeCnt * 3 + 2 < N) {
                    ans[r - 1] = ++threeNodeCnt * 3
                } else {
                    ans[r - 1] = otherNodeCnt / 2 * 3 + otherNodeCnt % 2 + 1
                    otherNodeCnt++
                }
            }
        }
    }

    println(ans.joinToString(" "))
}

fun readInputLine(): String {
    return readLine()!!
}
