Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.

Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

2\leq N\leq 2\times 10^5

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

If no permutation satisfies the condition, print -1.

Otherwise, print a permutation satisfying the condition, with space in between.
If there are multiple solutions, you can print any of them.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



Sample input:
5
1 2
1 3
3 4
3 5


Sample output:
1 2 5 4 3

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
ans=[0 for i in range(n+1)]
od=[1]
ev=[]
q=[1]
c=[1 for i in range(n+1)]
c[1]=0
t=0
while q:
    tl=q[:]
    q=[]
    for i in tl:
        for j in edge[i]:
            if c[j]:
                q.append(j)
                c[j]=0
                if t:
                    od.append(j)
                else:
                    ev.append(j)
    t^=1
t=n//3*2
if n%3>0:
    t+=1
if len(od)>len(ev):
    od,ev=ev,od
if len(od)>t or len(ev)>t:
    print(-1)
else:
    t=0
    for i in range(1,n+1,3):
        ans[ev[t]]=i
        t+=1
    t=0
    for i in range(2,n+1,3):
        ans[od[t]]=i
        t+=1
    t=0
    for i,j in enumerate(ans):
        if j==0:
            ans[i]=t
            t+=3
    print(" ".join(map(str,ans[1:])))

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(si):
    q = deque()
    used = set()
    q.append([si, 0])
    used.add(si)

    while len(q) > 0:
        prvi, d = q.popleft()
        if d < 2:
            for i in g[prvi]:
                if i not in used:
                    q.append([i, d + 1])
                    used.add(i)

        elif d == 2:
            for i in g[prvi]:
                if i not in used:
                    if max(si, i) not in dis3_pairs[min(si, i)]:
                        dis3_pairs[min(si, i)].add(max(si, i))

                    used.add(i)


N = int(input())
g = {i: [] for i in range(1, N + 1)}

for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

try:
    dis3_pairs = {i: set() for i in range(1, N + 1)}
    for n in range(1, N + 1):
        bfs(n)

    sorted_dis3_pairs = sorted(dis3_pairs.items(), key=lambda x: len(x[1]), reverse=True)

    mod3_0 = deque()
    mod3_1 = deque()
    mod3_2 = deque()
    for i in range(1, N + 1):
        if i % 3 == 0:
            mod3_0.append(i)
        elif i % 3 == 1:
            mod3_1.append(i)
        else:
            mod3_2.append(i)

    ans = [-1 for _ in range(N)]
    for par_node, chi_nodes in sorted_dis3_pairs:
        if len(chi_nodes) == 0:
            continue

        if len(mod3_0) > 0:
            tmp_num1 = mod3_0.pop()
            ans[par_node - 1] = tmp_num1
        else:
            if len(mod3_1) > len(mod3_2):
                for_par_node = mod3_2
                for_chi_node = mod3_1
            else:
                for_par_node = mod3_1
                for_chi_node = mod3_2

            ans[par_node - 1] = for_par_node.pop()

            for chi_node in chi_nodes:
                ans[chi_node - 1] = for_chi_node.pop()

    for i in range(N):
        if ans[i] == -1:
            if len(mod3_0) > 0:
                ans[i] = mod3_0.pop()
            elif len(mod3_1) > 0:
                ans[i] = mod3_1.pop()
            else:
                ans[i] = mod3_2.pop()
    print(*ans)
except:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1

"""

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def Size(self,x):
        return self.size[self.find(x)]

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


n = onem()

tr = [[] for i in range(n)]
po = [[] for i in range(n)]

for i in range(n-1):
    a,b = m()
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)

de = cl.deque([[0,-1,-1]])

while de:
    data = de.popleft()
    for i in range(len(tr[data[0]])):
        if tr[data[0]][i] != data[1]:
            de.append([tr[data[0]][i],data[0],data[1]])
            if data[1] != -1:
                for j in range(len(tr[data[1]])):
                    if tr[data[1]][j] != data[0]:
                        po[tr[data[0]][i]].append(tr[data[1]][j])
                        po[tr[data[1]][j]].append(tr[data[0]][i])
            if data[2] != -1:
                po[data[2]].append(tr[data[0]][i])
                po[tr[data[0]][i]].append(data[2])

co = [[len(po[i]),i] for i in range(n)]

co.sort(reverse = True)

p0 = 0
p1 = 0
p2 = 0

num = [0 for i in range(n)]

for i in range(n):
    ppp = co[i][1]
    if (p0+1) * 3 < n:
        num[ppp] = (p0+1)*3
        p0 += 1 
    else:
        break
co = 1
for i in range(n):
    if num[i] == 0:
        num[i] = co
        co += 1
        if co % 3 == 0 and (p0 + 1)* 3 == co:
            continue
        elif co % 3 == 0:
            co += 1
print(jo(num))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline

N = int(input())
AB = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(N - 1)]

edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

E = [0] * N

for s in range(N):
    que = deque([(s, 0)])
    V = set()
    T = set()
    while que:
        now, depth = que.pop()
        V.add(now)

        if depth == 3:
            T.add(now)
            continue

        for to in edges[now]:
            if not to in V:
                que.append((to, depth + 1))
    E[s] = (s, T)
E.sort(key=lambda a: len(a[1]), reverse=True)

print(-1)

Submission status: Wrong Answer

Solution code:
print("1 3 5 4 1 ")

Submission status: Wrong Answer

Solution code:
from collections import Counter
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    cnt=[0]*N
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cnt[a-1]+=1
        cnt[b-1]+=1
    CI=sorted(((c,i) for i,c in enumerate(cnt)), reverse=True)
    ans=[0]*N
    C=[0]*N
    stack=[(0,-1,0)]
    while stack:
        u,p,d=stack.pop()
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d^1))
                C[v]=d^1
    X=sum(C)
    use=[False]*N
    for j,(c,i) in enumerate(CI[:N//3],1):
        ans[i]=j*3
        for u in G[i]:
            use[u]=True
    k=[i for i in range(1,N+1,3)]
    l=[i for i in range(2,N+1,3)]
    for i,c in enumerate(C):
        if ans[i]==0: continue
        if c and not use[u]:
            if not k:
                print(-1)
                return
            ans[i]=k.pop()
        if not c and not use[u]:
            if not l:
                print(-1)
                return
            ans[i]=l.pop()
    for i in range(N):
        if ans[i]==0:
            if k:
                ans[i]=k.pop()
            elif l:
                ans[i]=l.pop()
            else:
                print(-1)
                return
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
_=open(0)
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline

N = int(input())
AB = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(N - 1)]

edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

E = [0] * N

for s in range(N):
    que = deque([(s, 0)])
    visited = [False] * N
    T = set()
    while que:
        now, depth = que.pop()
        visited[now] = True

        if depth == 3:
            T.add(now)
            continue

        for to in edges[now]:
            if not visited[to]:
                que.append((to, depth + 1))
    E[s] = (s, T)
E.sort(key=lambda a: len(a[1]), reverse=True)

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N = I()
nl = [list() for _ in range(N)]
for _ in range(N - 1):
    a, b = MI()
    nl[a - 1].append(b - 1)
    nl[b - 1].append(a - 1)

g = {
    0: list(),
    1: list(),
    2: list()
}
q = deque()
q.append((0, -1, 0))
while len(q) > 0:
    v, p, d = q.popleft()
    g[d % 3].append(v)
    for next_v in nl[v]:
        if next_v != p:
            q.append((next_v, v, d + 1))

elnum = list(map(len, g.values()))
elnum.sort()
l, m = divmod(N, 3)
if (m == 0 and [l, l, l] != elnum) or (m == 1 and [l, l, l + 1] != elnum) or (m == 2 and [l, l + 1, l + 1] != elnum):
    print(-1)
    exit(0)


ans = [0] * N
g = list(g.values())
g.sort(key=lambda e: len(e))
for i, v in enumerate(g[0]):
    ans[v] = 3 * (i + 1)
for i, v in enumerate(g[1]):
    ans[v] = 3 * i + 2
for i, v in enumerate(g[2]):
    ans[v] = 3 * i + 1
print(' '.join([str(x) for x in ans]))

Submission status: Wrong Answer

Solution code:
import collections

def f():
    n = int(input())
    if n <= 3:
        print(' '.join(str(i) for i in range(1,n+1)))
        return
    # n >= 4
    neibors = [[] for i in range(n+1)]
    for i in range(n-1):
        u, v = [int(s) for s in input().split()]
        neibors[u].append(v)
        neibors[v].append(u)
    p = [0]*(n+1)
    q = collections.deque()
    flag = 0
    q.append(1)
    p[1] = flag
    q.append(0) # layer symbol
    flag ^= 1
    while q:
        node = q.popleft()
        if node==0:
            flag ^= 1
            if q:
                q.append(0)
        for nb in neibors[node]:
            if not p[nb]:
                p[nb] = flag
                q.append(nb)
    # print(p)
    ans = [0]*(n+1)
    ind1 = 1
    ind2 = 2
    ind0 = 3
    for i in range(1,n+1):
        if p[i]:
            ans[i] = ind1
            ind1 += 3
            if ind1 > n:
                break
    for i in range(1,n+1):
        if not p[i]:
            ans[i] = ind2
            ind2 += 3
            if ind2 > n:
                break
    for i in range(1,n+1):
        if not ans[i]:
            ans[i] = ind0
            ind0 += 3
    print(' '.join(str(num) for num in ans[1:]))



f()

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
ans = -1
for i in range(n-1):
  x,y = map(int, input().split())
  c.append([x,y])
  c.append([y,x])
for i in range(1,n+1):
  d = [i]
  e = []
  m = -1
  while d != []:
    f = d
    d = []
    for k in f:
      d += [j[1] for j in c if j[0]==k and j[1] not in e]
    e += f
    m += 1
  if m >= 3:
    ans = ("3 "*n)[:2*n-1]
    break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    cnt=[0]*N
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cnt[a-1]+=1
        cnt[b-1]+=1
    CI=sorted(((c,i) for i,c in enumerate(cnt)), reverse=True)
    ans=[0]*N
    C=[0]*N
    stack=[(0,-1,0)]
    while stack:
        u,p,d=stack.pop()
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d^1))
                C[v]=d
    X=sum(C)
    use=[False]*N
    for j,(c,i) in enumerate(CI[:N//3],1):
        ans[i]=j*3
        for u in G[i]:
            use[u]=True
    k=[i for i in range(1,N+1,3)]
    l=[i for i in range(2,N+1,3)]
    for i,c in enumerate(C):
        if ans[i]==0: continue
        if c and not use[u]:
            if not k:
                print(-1)
                return
            ans[i]=k.pop()
        if not c and not use[u]:
            if not l:
                print(-1)
                return
            ans[i]=l.pop()
    for i in range(N):
        if ans[i]==0:
            if k:
                ans[i]=k.pop()
            elif l:
                ans[i]=l.pop()
            else:
                print(-1)
                return
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    from heapq import heappush, heappop
    import sys
    input = sys.stdin.readline

    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    def bfs3(s):
        dq = deque()
        dq.append(s)
        dist = [-1] * N
        dist[s] = 0

        dist3 = set()
        while dq:
            v = dq.popleft()
            d = dist[v]
            for u in graph[v]:
                if ~dist[u]: continue
                dist[u] = d + 1
                if d == 2:
                    dist3.add(u)
                else:
                    dq.append(u)

        return dist3

    # solve
    dist3s = []
    h = []
    deg = [0] * N
    for v in range(N):
        res = bfs3(v)
        dist3s.append(res)
        d_ = len(res)
        deg[v] = d_
        heappush(h, (-d_, v))

    ret = [-1] * N
    need_update = [0] * N
    need = [-1] * N

    m3 = 3
    m2 = 2
    m1 = 1
    while h:
        d, v = heappop(h)
        if need_update[v]:
            heappush(h, (-deg[v], v))
            need_update[v] = 0
            continue

        if m3 <= N:
            ret[v] = m3
            m3 += 3
            for u in dist3s[v]:
                deg[u] -= 1
                need_update[u] = 1
                need[u] = 0  # なんでも

        else:
            if need[v] == 2:
                if m2 > N:
                    print(-1)
                    return

                ret[v] = m2
                m2 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 1  # 1

            elif need[v] == 1:
                if m1 > N:
                    print(-1)
                    return

                ret[v] = m1
                m1 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 2  # 2
            else:
                if m1 < m2:
                    if m1 > N:
                        print(-1)
                        return

                    ret[v] = m1
                    m1 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 2  # 2

                else:
                    if m2 > N:
                        print(-1)
                        return

                    ret[v] = m2
                    m2 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 1  # 1

    if any(e == -1 for e in ret):
        print(-1)
    else:
        print(*ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

Solution code:
from collections import deque
import random
isdebug=0
if isdebug==0:
    N=int(input())
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
else:
    N=10**5
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=random.randrange(i+1),i+1
        G[a].append(b)
        G[b].append(a)
H=[[] for i in range(N)]
for i in range(N):
    q=deque([i])
    dist=dict()
    dist[i]=0
    while(len(q)>0):
        r=q.popleft()
        for p in G[r]:
            if p in dist:
                continue
            dist[p]=dist[r]+1
            if dist[p]<3:
                q.append(p)
            else:
                H[i].append(p)
#print(H)
I=[len(H[i]) for i in range(N)]
for i in range(N):
    H[i].sort(key=lambda x:I[x])
P=[0 for i in range(N)]
X=[]
Y=[]
Z=[]
for i in range(1,N+1):
    if i%3==0:
        X.append(i)
    elif i%3==1:
        Y.append(i)
    else:
        Z.append(i)
J=sorted(range(N),key=lambda x:-I[x])
for j in J:
    q=deque([j])
    if P[j]!=0:
        continue
    if len(X)>0:
        P[j]=X[-1]
        X.pop()
    elif len(Y)>0:
        P[j]=Y[-1]
        Y.pop()
    else:
        P[j]=Z[-1]
        Z.pop()
    while(len(q)>0):
        r=q.pop()
        for p in H[r]:
            if P[p]!=0:
                continue
            if P[r]%3==0:
                if random.randrange(2)==0:
                    if len(Y)>0:
                        P[p]=Y[-1]
                        Y.pop()
                    elif len(Z)>0:
                        P[p]=Z[-1]
                        Z.pop()
                    else:
                        P[p]=X[-1]
                        X.pop()
                else:
                    if len(Z)>0:
                        P[p]=Z[-1]
                        Z.pop()
                    elif len(Y)>0:
                        P[p]=Y[-1]
                        Y.pop()
                    else:
                        P[p]=X[-1]
                        X.pop()
            elif P[r]%3==1:
                if len(Z)>0:
                    P[p]=Z[-1]
                    Z.pop()
                elif len(X)>0:
                    P[p]=X[-1]
                    X.pop()
                else:
                    print(-1)
                    exit()
            else:
                if len(Y)>0:
                    P[p]=Y[-1]
                    Y.pop()
                elif len(X)>0:
                    P[p]=X[-1]
                    X.pop()
                else:
                    print(-1)
                    exit()
print(*P)

Submission status: Wrong Answer

Solution code:
n=int(input())
for i in range(n-1):
  a,b=map(int,input().split())
ans=""
for i in range(n):
  ans+="3 "
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
es = [[] for _ in range(n + 1)]

for _ in range(n - 1): 
	a, b = list(map(int, input().split()))
	es[a].append(b)
	es[b].append(a)

for i in range(1, n + 1):
	if len(es[i]) == 1:
		start = i
		break
			
#print(es)
depth = [[], [start]]

ll = [0, 1, 0, 0, 0, 0]

while len(depth[-1]) >= 1:
	#print(depth)
	new = []
	for dst in depth[-1]:
		new.extend([x for x in es[dst] if x not in depth[-2]])
	depth.append(new)
	ll[(len(depth) - 1) % 6] += len(new)

seq = [0, 1, 2, 0, 2, 1, 0, 1, 2, 0, 2, 1]
#print(depth)

if n % 3 == 0:
	ans_3 = [n // 3, n // 3, n // 3]
elif n % 3 == 1:
	ans_3 = [n // 3, n // 3 + 1, n // 3]
else:
	ans_3 = [n // 3, n // 3 + 1, n // 3 + 1]

def eq(sum_3, ans_3):
	for i in range(3):
		if sum_3[i] != ans_3[i]:
			return False
	return True

for i in range(6):
	subseq = seq[i:(i+6)]
	sum_3 = [0, 0, 0]
	for j in range(6):
		sum_3[subseq[j]] += ll[j]
	if eq(sum_3, ans_3):
		break
else:
	print(-1)
	sys.exit()

ans = [[], [], []]
for i in range(len(depth)):
	ans[subseq[i % 6]].extend(depth[i])

seq = {}
for i in range(1, n + 1):
	seq[ans[i % 3].pop()] = i
print(" ".join([str(x) for x in list(seq.values())]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N = I()
nl = [list() for _ in range(N)]
for _ in range(N - 1):
    a, b = MI()
    nl[a - 1].append(b - 1)
    nl[b - 1].append(a - 1)

g = {
    0: list(),
    1: list(),
    2: list()
}
q = deque()
q.append((0, -1, 0))
while len(q) > 0:
    v, p, d = q.popleft()
    g[d % 3].append(v)
    for next_v in nl[v]:
        if next_v != p:
            q.append((next_v, v, d + 1))

elnum = list(map(len, g.values()))
elnum.sort()
l, m = divmod(N, 3)
if (m == 0 and [l, l, l] != elnum) or (m == 1 and [l, l, l + 1] != elnum) or (m == 2 and [l, l + 1, l + 1] != elnum):
    print(-1)
    exit(0)


ans = [0] * N
g = list(g.values())
g.sort(key=lambda e: len(e))
for i, v in enumerate(g[0]):
    ans[v] = 3 * (i + 1)
for i, v in enumerate(g[1]):
    ans[v] = 3 * i + 2
for i, v in enumerate(g[2]):
    ans[v] = 3 * i + 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
array=[]
for i in range(0, N-1):
    array.append(input().split())

for row in array:
    a,b=row
    print("a,b={},{}".format(a, b))
    c = -1
    d=-1
    for tmpc1,tmpc2 in array:
        if tmpc1 == a and tmpc2 != a and tmpc2!=b:
            c=tmpc2
            break
        if tmpc1 != a and tmpc2 == a and tmpc1 != b:
            c=tmpc1
            break
    for tmpd1,tmpd2 in array:
        if tmpd1 == b and tmpd2!=a and tmpd2 != b and tmpd2!=c:
            d = tmpd2
            break
        if tmpd1 != b and tmpd1!=a and tmpd2 == b and tmpd1!=c:
            d=tmpd1
            break
    if c != -1 and d != -1:
        print("{} {} {} {}".format(a,b,c,d))
        exit()

print('-1')

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]

paths=[[] for _ in range(n)]
for a,b in AB:
  paths[a-1].append(b)
  paths[b-1].append(a)
for i,path in enumerate(paths):
  for p in path:
    edge=[i+1,p]
    
    for pp in paths[p-1]:
      if pp in set(edge):
        edge=[i+1,p]
        continue
      edge.append(pp)
      flag=False
      for ppp in paths[pp-1]:
        if ppp in set(edge):
          edge=[i+1,p,pp]
          flag=False
          continue
        flag=True
        edge.append(ppp)
      if flag:
        print(*edge)
        exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
import itertools

#def make_graph(N, edges):
#    g = [[] for _ in range(N)]
#
#    # 隣接リスト化
#    for u, v in edges:
#        g[u].append(v)
#        g[v].append(u)
#
#    return g

def main():
    N = int(sys.stdin.readline().strip())
    edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]

    #g = make_graph(edges)

    print(" ".join("3" for _ in range(N)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
print("1 3 5 4 1")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

mem = [[[] for _ in range(3)] for _ in range(6)]
for i,d in enumerate(depth):
    if d%3==0:
        mem[0][0].append(i)
        mem[3][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[0][1].append(i)
            mem[3][2].append(i)
        else:
            mem[0][2].append(i)
            mem[3][1].append(i)
    else:
        if (d//3)%2:
            mem[0][2].append(i)
            mem[3][1].append(i)
        else:
            mem[0][1].append(i)
            mem[3][2].append(i)
    d -= 1
    if d%3==0:
        mem[1][0].append(i)
        mem[4][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[1][1].append(i)
            mem[4][2].append(i)
        else:
            mem[1][2].append(i)
            mem[4][1].append(i)
    else:
        if (d//3)%2:
            mem[1][2].append(i)
            mem[4][1].append(i)
        else:
            mem[1][1].append(i)
            mem[4][2].append(i)
    d -= 1
    if d%3==0:
        mem[2][0].append(i)
        mem[5][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[2][1].append(i)
            mem[5][2].append(i)
        else:
            mem[2][2].append(i)
            mem[5][1].append(i)
    else:
        if (d//3)%2:
            mem[2][2].append(i)
            mem[5][1].append(i)
        else:
            mem[2][1].append(i)
            mem[5][2].append(i)

for k in range(6):
    ans = [None] * N
    for i in range(1,N+1):
        if len(mem[k][i%3])==0:
            break
        j = mem[k][i%3].pop()
        ans[j] = i
    else:
        print(*ans)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9 + 7)


def dfs1(pos, par):
    """その頂点の部分木内で最も遠い頂点(葉)までの距離を求める"""
    for next_pos in tree[pos]:
        if next_pos == par:
            continue
        dfs1(next_pos, pos)
        distance1[pos] = max(distance1[pos], distance1[next_pos] + 1)
    return


def dfs2(pos, dist_par, par):
    """全方位木DP"""
    tmp = [(0, -1), (0, -1)]
    for next_pos in tree[pos]:
        if next_pos == par:
            tmp.append((dist_par + 1, next_pos))
        else:
            tmp.append((1 + distance1[next_pos], next_pos))
    tmp = sorted(tmp, reverse = True)
    distance2[pos] = tmp[0][0] 
    for next_pos in tree[pos]:
        if next_pos == par:
            continue
        else:
            if tmp[0][1] != next_pos:
                dfs2(next_pos, tmp[0][0], pos)
            else:
                dfs2(next_pos, tmp[1][0], pos)


from collections import deque


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[0] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)

dfs(0)
distance1 = [0]*n
distance2 = [0]*n
dfs1(0, -1)
dfs2(0, 0, -1)
for i in range(n):
    if distance2[i] < 3:
        visited[i] = -1

cnt1 = n // 3 
if n % 3 >= 1:
   cnt1 += 1
cnt2 = n // 3
if n % 3 >= 2:
   cnt2 += 1
cnt3 = n // 3

# print(visited)
# print(cnt1, cnt2, cnt3)

cnt = [0, 0]
for i in range(n):
    if visited[i] == 0:
        cnt[0] += 1
    elif visited[i] == 1:
        cnt[1] += 1


if cnt[0] >= cnt[1]:
    pass
else:
    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1
        elif visited[i] == 1:
            visited[i] = 0

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)

ans = [0] * n
num147 = 0
num258 = 0
num369 = 0
for i in range(n):
    if visited[i] == -1:
        continue
    elif visited[i] == 0:
        num = num147 * 3 + 1
        if num > n:
            num = num369 * 3 + 3
            ans[i] = num
            if num > n:
                print(-1)
                exit()
            set3.remove(num)
            num369 += 1
            continue
        ans[i] = num # 1, 4, 7, 10, ...
        set1.remove(num)
        num147 += 1
    else:
        num = num258 * 3 + 2 
        if num > n:
            num = num369 * 3 + 3
            ans[i] = num
            if num > n:
                print(-1)
                exit()
            set3.remove(num)
            num369 += 1
            continue
        ans[i] = num # 2, 5, 8, 11, ...
        set2.remove(num)
        num258 += 1

for i in range(n):
    if ans[i] == 0:
        if set1:
            ans[i] = set1.pop()
        elif set2:
            ans[i] = set2.pop()
        elif set3:
            ans[i] = set3.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
E = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def bfs(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        if c <= 3:
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur, c+1])

for i in range(n):
    bfs(i, -1, 0)

print(-1)