Problem:


Score : 800 points

Problem Statement

Takahashi and Aoki will play a game on a tree.
The tree has N vertices numbered 1 to N, and the i-th of the N-1 edges connects Vertex a_i and Vertex b_i.

At the beginning of the game, each vertex contains a coin.
Starting from Takahashi, he and Aoki will alternately perform the following operation:

Choose a vertex v that contains one or more coins, and remove all the coins from v.

Then, move each coin remaining on the tree to the vertex that is nearest to v among the adjacent vertices of the coin's current vertex.

The player who becomes unable to play, loses the game.
That is, the player who takes his turn when there is no coin remaining on the tree, loses the game.
Determine the winner of the game when both players play optimally.

Constraints

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

1 \leq a_i, b_i \leq N

a_i \neq b_i

The graph given as input is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}

Output

Print First if Takahashi will win, and print Second if Aoki will win.

Sample Input 1

3
1 2
2 3

Sample Output 1

First

Here is one possible progress of the game:

Takahashi removes the coin from Vertex 1. Now, Vertex 1 and Vertex 2 contain one coin each.

Aoki removes the coin from Vertex 2. Now, Vertex 2 contains one coin.

Takahashi removes the coin from Vertex 2. Now, there is no coin remaining on the tree.

Aoki takes his turn when there is no coin on the tree and loses.

Sample Input 2

6
1 2
2 3
2 4
4 6
5 6

Sample Output 2

Second

Sample Input 3

7
1 7
7 4
3 4
7 5
6 3
2 1

Sample Output 3

First



Sample input:
3
1 2
2 3


Sample output:
First

Submission status: Wrong Answer

Solution code:
import heapq
INF = 10**9

n = int(input())
edge = [[] for _ in range(n)]

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def reset(self):
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest in self.adj[src]:
                cost = 1
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        return self.dist 

for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

dij = Dijkstra(edge)
dist = dij.calc(0)
left_edge = dist.index(max(dist))
dij.reset()
dist = dij.calc(left_edge)
diam = max(dist)
if diam == 0 or diam == 2:
    print("First")
elif diam % 2 == 0:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())

g = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append((1,b))
    g[b].append((1,a))
d = dijkstra(g,N,0)
r = 0
n = 0
for i in range(N):
    if r < d[i]:
        r = d[i]
        n = i
r = max(dijkstra(g,N,n))
if r == 0 or r == 2:
    print('First')
elif r == 1:
    print('Second')
elif r%2==1:
    print('First')
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
n = int(input())
if n == 1:
    print('Second')
    exit()

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

used = [True]*n
q = []
used[0] = False
for e in edge[0]:
    q.append(e)
    used[e] = False
while q:
    tank = []
    for elt in q:
        for e in edge[elt]:
            if used[e]:
                tank.append(e)
                used[e] = False
    if len(tank) == 0:
        start = q[0]
    q = tank

used = [True]*n
q = []
used[start] = False
for e in edge[start]:
    q.append(e)
    used[e] = False
d = 1
while q:
    tank = []
    for elt in q:
        for e in edge[elt]:
            if used[e]:
                tank.append(e)
                used[e] = False
    if tank:
        d += 1
    q = tank

if d%3 == 1:
    print('Second')
else:
    print('First')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [[] for i in range(N)]
for n in range(N-1):
    a,b = map(int, input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)
#print(A)


from collections import deque
def dfs(node):
    st = deque()
    push, pop = st.append, st.pop
    push(node)
    cnt = [0]*N
    cnt[node] = 1
    while st:
        now = pop()
        for n in A[now]:
            if cnt[n] == 0:
                push(n)
            cnt[n] = 1
    return now

def dfs_L(node):
    st = deque()
    push, pop = st.append, st.pop
    push([node,0])
    cnt = [0]*N
    cnt[node] = 1
    L_list = []
    while st:
        [now,L] = pop()
        L_list.append(L)
        for n in A[now]:
            if cnt[n] == 0:
                push([n,L+1])
            cnt[n] = 1
    return max(L_list)
            

step1 = dfs(0)
length = dfs_L(step1)
if length%3 == 1:
    print('Second')
else:
    print('First')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])
        if node in treeQ:
            treeQ.remove(node)

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if decidedFlg:
            break

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])
        if node in treeQ:
            treeQ.remove(node)

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば隣接ノードのコスト + 1で更新
                cost = nextCost + 1

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])
        if node in treeQ:
            treeQ.remove(node)

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば隣接ノードのコスト + 1で更新
                cost = nextCost + 1

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans, diameter)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = -1
while(treeQ):
  
    tQ = set()
    for node in treeQ:
        if costDict[node]>0:
            break
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            # print(node,nextCost,nextCost)
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1

# print(diameter)
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])
        if node in treeQ:
            treeQ.remove(node)

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost <= 0:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])
        if node in treeQ:
            treeQ.remove(node)

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    tQ = set()
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = -1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = costDict[node], 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = -1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = costDict[node], 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


N = int(input())
# 例外処理
if (N == 1):
    quit()

tree = defaultdict(set)
tree_main = defaultdict(set)
for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].add(b)
    tree[b].add(a)
    tree_main[a].add(b)
    tree_main[b].add(a)

def longest_path(tree, from_node=1):
    cnt = 1

    nearest_nodes = list(tree[from_node])
    while len(nearest_nodes) > 0:
        for one_step_node in nearest_nodes:
            for two_step_node in tree[one_step_node]:
                if two_step_node != from_node:
                    tree[two_step_node].remove(one_step_node)
                    tree[two_step_node].add(from_node)
                    tree[from_node].add(two_step_node)
            tree[from_node].remove(one_step_node)
        cnt += 1
        nearest_nodes = list(tree[from_node])

    return one_step_node, cnt


far, _ = longest_path(tree)
_, n = longest_path(tree_main, far)
print("Second" if n % 3 == 2 else "First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np
import sys
input = sys.stdin.readline


N = int(input())
# 例外処理
if (N == 1):
    print("First")
    quit()

tree = defaultdict(set)
tree_main = defaultdict(set)
for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].add(b)
    tree[b].add(a)
    tree_main[a].add(b)
    tree_main[b].add(a)

print(tree.keys())


def longest_path(tree, from_node=1):
    cnt = 1

    nearest_nodes = list(tree[from_node])
    while len(nearest_nodes) > 0:
        for one_step_node in nearest_nodes:
            for two_step_node in tree[one_step_node]:
                print(from_node, one_step_node, two_step_node)
                if two_step_node != from_node:
                    tree[two_step_node].remove(one_step_node)
                    tree[two_step_node].add(from_node)
                    tree[from_node].add(two_step_node)
            tree[from_node].remove(one_step_node)
        cnt += 1
        nearest_nodes = list(tree[from_node])

    return one_step_node, cnt


far, _ = longest_path(tree)
_, n = longest_path(tree_main, far)
print("Second" if n % 3 == 2 else "First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])
        if node in treeQ:
            treeQ.remove(node)

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = costDict[node]
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])
        if node in treeQ:
            treeQ.remove(node)

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = -1
while(treeQ):
    tQ = set()
    for node in treeQ:
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costDict[node] = cost
        if qNode != -1:
            tQ.add(qNode)

    treeQ = tQ

# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
print(["Second","First"][int(input())%2])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

treeDict = defaultdict(list)
for ab in abList:
    a, b = ab
    treeDict[a].append(b)
    treeDict[b].append(a)

costDict = defaultdict(int)
treeQ = set()
for i in range(1, N + 1):
    if len(treeDict[i]) == 1:
        costDict[i] = 1
        treeQ.add(treeDict[i][0])

treeMaxLen = 0
continueFlg = True
while(continueFlg):
    tQ = set()
    for i, n1 in enumerate(treeQ):
        decidedFlg = True
        cost = -1
        qTemp = -1
        for j, n2 in enumerate(treeDict[n1]):
            if costDict[n2] == 0:
                if not decidedFlg:
                    cost = -1
                    qTemp = -1
                    break
                qTemp = n2
                decidedFlg = False
            else:
                cost = max(cost, costDict[n2] + 1)

        if decidedFlg:
            firstLen, secondLen = -1, -1
            for i, n2 in enumerate(costDict):
                if costDict[n2] > firstLen:
                    secondLen = firstLen
                    firstLen = costDict[n2]
                elif costDict[n2] > secondLen:
                    secondLen = costDict[n2]
            treeMaxLen = firstLen + secondLen + 1
            continueFlg = False
            break

        if cost != -1:
            costDict[n1] = cost
            tQ.add(qTemp)
    treeQ = tQ

ans = "First" if treeMaxLen % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]

treeDict = defaultdict(list)
for ab in abList:
    a, b = ab
    treeDict[a].append(b)
    treeDict[b].append(a)

costDict = defaultdict(int)
treeQ = set()
for i in range(1, N + 1):
    if len(treeDict[i]) == 1:
        costDict[i] = 1
        treeQ.add(treeDict[i][0])

treeMaxLen = 0
continueFlg = True
while(continueFlg):
    tQ = []
    for i, n1 in enumerate(treeQ):
        decidedFlg = True
        cost = -1
        qTemp = -1
        for j, n2 in enumerate(treeDict[n1]):
            if costDict[n2] == 0:
                if not decidedFlg:
                    cost = -1
                    qTemp = -1
                    break
                qTemp = n2
                decidedFlg = False
            else:
                cost = max(cost, costDict[n2] + 1)

        if decidedFlg:
            firstLen, secondLen = -1, -1
            for i, n2 in enumerate(costDict):
                if costDict[n2] > firstLen:
                    secondLen = firstLen
                    firstLen = costDict[n2]
                elif costDict[n2] > secondLen:
                    secondLen = costDict[n2]
            treeMaxLen = firstLen + secondLen + 1
            continueFlg = False
            break

        if cost != -1:
            costDict[n1] = cost
            tQ.append(qTemp)

    treeQ = tQ

ans = "First" if treeMaxLen % 3 != 2 else "Second"
print(ans)

Submission status: Wrong Answer

Solution code:
def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = [0]
    while q:
        v = q.pop(0)
        ev = V[v]
        for w in E[v]:
            if V[w] == -1:
                V[w] = ev + 1
                q.append(w)
    s = V.index( max(V))
    p = [s]
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.pop(0)
        ev = W[v]
        for w in E[v]:
            if W[w] == -1:
                W[w] = ev + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
print( diameter(N,E))
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)