3-Coloring

def three_coloring(n, edges):
    color = [-1] * n  # To store colors for nodes (1-based)
    visited = [False] * n  # To track visited nodes
    in_cycle = [False] * n  # To mark nodes that are part of a cycle

    def dfs(node):
        stack = []
        current = node
        while not visited[current]:
            visited[current] = True
            stack.append(current)
            current = edges[current] - 1  
        if current in stack:   
            cycle_start = stack.index(current)
            return stack[cycle_start:]  
        return []
 
    def color_cycle(cycle):
        for i, node in enumerate(cycle):
            color[node] = (i % 3) + 1  
            in_cycle[node] = True   

    
    for i in range(n):
        if not visited[i]:
            cycle = dfs(i)
            if cycle:
                color_cycle(cycle)

   
    for i in range(n):
        if color[i] == -1:  
            color[i] = (color[edges[i] - 1] % 3) + 1  

    print(" ".join(map(str, color)))

 
n = int(input())
edges = list(map(int, input().split()))
three_coloring(n, edges)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER