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: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class breadth(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0
        self.visit = ["no" for i in range(len(graph) + 1)]
        self.visit[s] = "yes"
        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        while self.Q:
            dist_u, u = heappop(self.Q)
            for v in self.g[u]:
                if self.visit[v] == "yes":
                    continue
                else:
                    self.dist[v] = dist_u + 1
                    self.prev[v] = u
                    self.visit[v] = "yes"
                    heappush(self.Q, (self.dist[v], v))

    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


N = int(input())
if N == 1:
	print("First")
else:
	g_a = Graph()
	for i in range(N - 1):
		a, b = getlist()
		g_a.add_edge(a, b)
		g_a.add_edge(b, a)
	
	s = 1
	E = breadth(g_a, s)
	x = 0
	for i in E.dist:
		if E.dist[i] > x:
			x = E.dist[i]
			y = i
	F = breadth(g_a, y)
	x = 0
	for i in F.dist:
		if F.dist[i] > x:
			x = F.dist[i]
			y = i

if x % 3 == 0 or x % 3 == 2:
	print("First")
else:
	print("Second")

Submission status: Runtime Error

Solution code:
N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

if all(len(e)<=2 for e in es):
    print('First' if N%2 else 'Second')
    exit()
assert False

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class breadth(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0
        self.visit = ["no" for i in range(len(graph) + 1)]
        self.visit[s] = "yes"
        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        while self.Q:
            dist_u, u = heappop(self.Q)
            for v in self.g[u]:
                if self.visit[v] == "yes":
                    continue
                else:
                    self.dist[v] = dist_u + 1
                    self.prev[v] = u
                    self.visit[v] = "yes"
                    heappush(self.Q, (self.dist[v], v))

    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

N = int(input())
g_a = Graph()
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    g_a.add_edge(a, b)
    g_a.add_edge(b, a)

s = 1
E = breadth(g_a, s)
x = 0
for i in E.dist:
    if E.dist[i] > x:
        x = E.dist[i]
        y = i

F = breadth(g_a, y)
x = 0
for i in F.dist:
    if F.dist[i] > x:
        x = F.dist[i]
        y = i

if x % 3 == 0 or x % 3 == 2:
	print("First")
else:
	print("Second")

Submission status: Runtime Error

Solution code:
n=int(input())
l=[0 for i in range(n)]
L=[list(map(int,input().split())) for i in range(n-1)]
ct=0
for i in range(n-1):
  l[L[i][0]-1]+=1
  l[L[i][1]-1]+=1
x=1
for i in range(n):
  if l[i]%2==1 and l[i]>x:
    x=l[i]
xn=l.index(x)
ctx=0
for j in range(n-1):
  if L[j][0]==xn+1:
    if l[L[j][1]-1]%2==1:ctx+=1
  elif L[j][1]==xn+1:
    if l[L[j][0]-1]%2==1:ctx+=1

if ctx%2==1 or x<3:print('First')
else:print('Second')

Submission status: Runtime Error

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

def dfs(idx, con, visited):
    visited[idx] = True
    max_depth = 0
    max_len = 0
    depths = []
    if idx > len(con):
        return max_depth, max_len
    for v in con[idx]:
        if v < len(visited) and not visited[v]:
            max_d, max_l = dfs(v, con, visited)
            max_len = max(max_len, max_l)
            depths.append(max_d + 1)
    if len(depths) > 0:
        depths.sort(reverse=True)
        max_depth = depths[0]
        if len(depths) > 1:
            max_len = max(max_len, depths[0] + depths[1])
        else:
            max_len = max(max_len, depths[0])
    visited[idx] = False
    return max_depth, max_len


def solve(N: int, A: "List[int]", B: "List[int]"):
    con = [[] for _ in range(N)]
    for i in range(len(A)):
        a = A[i] - 1
        b = B[i] - 1
        con[a].append(b)
        con[b].append(a)
    #print(con)
    visited = [False] * N
    max_depth, max_len = dfs(0, con, visited)
    #print(max_len)
    if (max_len + 1) % 3 == 2:
        ret = 'Second'
    else:
        ret = 'First'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.edges = []
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

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

  leaves = [n for n in nodes if len(n.edges) == 1]

  while True:
    leaf = leaves.pop(0)
    parent = leaf.edges[0]

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

def dfs(idx, con, visited):
    visited[idx] = True
    max_depth = 0
    max_len = 0
    depths = []
    for v in con[idx]:
        if not visited[v]:
            max_d, max_l = dfs(v, con, visited)
            max_len = max(max_len, max_l)
            depths.append(max_d + 1)
    return 0, 0
    if len(depths) > 0:
        depths.sort(reverse=True)
        max_depth = depths[0]
        if len(depths) > 1:
            max_len = max(max_len, depths[0] + depths[1])
        else:
            max_len = max(max_len, depths[0])
    return max_depth, max_len


def solve(N: int, A: "List[int]", B: "List[int]"):
    con = [[] for _ in range(N)]
    for i in range(len(A)):
        a = A[i] - 1
        b = B[i] - 1
        con[a].append(b)
        con[b].append(a)
    #print(con)
    visited = [False] * N
    max_depth, max_len = dfs(0, con, visited)
    #print(max_len)
    if (max_len + 1) % 3 == 2:
        ret = 'Second'
    else:
        ret = 'First'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import networkx as nx

# この問題はグラフの最大経路を各ターンに1or2減らし、自分のターンに0にした方が負けというゲームであると言える
# 先攻のターンの時点で最後に枝数が1つなら後攻が、2つか3つなら先攻が勝つ→最大経路を3で割った余りで場合分け
# 後攻は先行の手に関係なく１ターンの枝数の減少を3にできる→初期が3n+1なら後攻が必勝
# 先攻は常に3n or 3n+2を維持すれば勝てる、これは3nの時は1を3n+2の時は2を出していれば可能
# つまり最大経路が3n or 3n+2なら先行、3n+1なら後攻が勝つ

Submission status: Runtime Error

Solution code:
from functools import reduce
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

conn = [len(v) for v in adj]
# print(conn)
max_node = conn.index(max(conn))
# print(max_node)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1:
        return dist
    else:
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                return dfs(n, cur, dist+1)


dist = []
# print("dist")
for nex in adj[max_node]:
    #print(dfs(nex, max_node, 1))
    dist.append(dfs(nex, max_node, 1))


def xor(x, y):
    return x ^ y


if reduce(xor, dist) == 0:
    ans = "First"
else:
    ans = "Second"
print(ans)

Submission status: Runtime Error

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

T = [[0] * N for _ in range(N)]
R = {}
for a, b in ab:
  T[a - 1][b - 1] = 1
  T[b - 1][a - 1] = 1
  if a - 1 in R:
    R[a - 1].append(b - 1)
  else:
    R[a - 1] = [b - 1]
  if b - 1 in R:
    R[b - 1].append(a - 1)
  else:
    R[b - 1] = [a - 1]

L = [0] * N
L[0] = 1
F = []
RL = {}
RL[1] = [0]
RL[2] = []
for i in R[0]:
  F.append(i)
  L[i] = 2
  RL[2].append(i)

k = 2
while F != []:
  k += 1
  Ft = []
  RL[k] = []
  for i in F:
    for j in R[i]:
      if L[j] == 0:
        L[j] = k
        Ft.append(j)
        RL[k].append(j)
  F = Ft

d = 0
D = [0] * N
for i in range(k - 1, 0, -1):
  for j in RL[i]:
    for k in R[j]:
      if L[k] == i - 1:
        if D[k] == 0:
          D[k] = D[j] + 1
          d = max(d, D[j] + 1)
        else:
          d = max(d, D[j] + D[k] + 1)
          D[k] = max(D[k], D[j] + 1)

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

Submission status: Runtime Error

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

def dfs(idx, con, visited):
    visited[idx] = True
    max_depth = 0
    max_len = 0
    depths = []
    for v in con[idx]:
        if not visited[v]:
            max_d, max_l = dfs(v, con, visited)
            max_len = max(max_len, max_l)
            depths.append(max_d + 1)
    if len(depths) > 0:
        depths.sort(reverse=True)
        max_depth = depths[0]
        if len(depths) > 1:
            max_len = max(max_len, depths[0] + depths[1])
        else:
            max_len = max(max_len, depths[0])
    return max_depth, max_len


def solve(N: int, A: "List[int]", B: "List[int]"):
    con = [[] for _ in range(N)]
    for i in range(len(A)):
        a = A[i] - 1
        b = B[i] - 1
        con[a].append(b)
        con[b].append(a)
    #print(con)
    visited = [False] * N
    max_depth, max_len = dfs(0, con, visited)
    #print(max_len)
    if (max_len + 1) % 3 == 2:
        ret = 'Second'
    else:
        ret = 'First'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# グラフの最長経路が-1か-2かを選べる
N = int(input())
edge = [[] for _ in range(N)]
INF = 10**18
for _ in range(N-1):
  a,b = map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

opposite = 0
max_dist = 0
def f(d,x):
  global max_dist,opposite
  dx = d[x]
  if dx > max_dist:
    opposite = x
    max_dist = dx
  for y in edge[x]:
    if d[y] == INF:
      d[y] = dx + 1
      f(d,y)

# 0からの距離
d = [INF] * N
d[0] = 0
f(d,0)

v = opposite
d = [INF] * N
d[v] = 0
f(d,v)

X = max_dist

ans = 'First' if max_dist%3 != 1 else 'Second'
print(ans)

Submission status: Runtime Error

Solution code:
def getlist():
	return list(map(int, input().split()))

N = int(input())
for i in range(N):
	a, b = getlist()


if N % 2 == 1:
	print("First")
else:
	print("Second")

Submission status: Runtime Error

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
if N % 2 != 0 :
    print("First")
else :
    print("Second")

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, a, b):
        self.no = a
        self.edges = [b]
        self.coin = 1


def max_depth(N, edges, edge, depth, parent_no):
    if edge.coin > 0:
        depth += 1
    max = depth
    if edge.edges:
        for id in edge.edges:
            if id != parent_no:
                t = max_depth(N, edges, edges[id], depth, edge.no)
                if t > max:
                    max = t
    return max


N = int(input())
X = [[0] * 2 for i in range(N - 1)]
edges = {}

for i in range(N - 1):
    a, b = list(map(int, input().split()))
    ea = edges.get(a)
    if ea:
        ea.edges.append(b)
    else:
        edges[a] = Node(a, b)
    eb = edges.get(b)
    if eb:
        eb.edges.append(a)
    else:
        edges[b] = Node(b, a)

min = 999999999
for i in range(1, N + 1):
    m = max_depth(N, edges, edges[i], 0, -1)
    if m < min:
        min = m
if min % 2 == 0:
    print("First")
else:
    print("Second")

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())


ans = N % 2


if ans == 0:
    print("Secound")
else:
    print("First")

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for i in range(N)]
connect = [0] * N
for i in range(N-1):
  a, b = map(int,input().split())
  edge[a-1] += [b-1]
  edge[b-1] += [a-1]
  connect[a-1]+=1
  connect[b-1]+=1

bunki = []
for i in range(N):
  if connect[i] >= 3:
    bunki += [i]
flag = 0
for p in bunki:
  ell = 0
  for q in edge[p]:
    if connect[q] > 1:
      ell += 1
  if ell > 1:
    flag = 1#Firstが勝てる
p = bunki.pop()
if connect[p] == N-1:
  flag = 1
  
if flag:
  print("First")
else:
  print("Second")

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N = int(readline())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
def bfs(s):
    dist = [None]*N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d
u, _ = bfs(0)
v, d = bfs(u)

memo = [-1]*(d+2)
memo[0] = 0
memo[1] = 1
memo[2] = 0
def dfs(d):
    if memo[d] != -1:
        return memo[d]
    if dfs(d-1) == 0 or dfs(d-2) == 0:
        memo[d] = 1
        return 1
    memo[d] = 0
    return 0
print("First" if dfs(d+1) else "Second")

Submission status: Runtime Error

Solution code:
from sys import stdin
def main():
    n = int(stdin.readline())
    e = [[] for _ in xrange(n)]
    for line in stdin:
        x, y = map(int, line.split())
        x -= 1
        y -= 1
        e[x].append(y)
        e[y].append(x)
    d = [None] * n
    st = []
    pu = st.append
    po = st.pop
    pu(0)
    d[0] = 0
    while st:
        x = po()
        for y in e[x]:
            if d[y] is None:
                d[y] = d[x] + 1
                pu(y)
    y = 0
    for i, x in enumerate(d):
        if y < x:
            y = x
            j = i
    d = [None] * n
    pu(j)
    d[j] = 0
    while st:
        x = po()
        for y in e[x]:
            if d[y] is None:
                d[y] = d[x] + 1
                pu(y)
    x = max(d)
    print 'Second' if x % 3 == 1 else 'First'
main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2 * 10 ** 5)


def dfs(v, p, links):
    farthest_d = 0
    farthest_v = v

    for u in links[v]:
        if u == p:
            continue
        res_d, res_v = dfs(u, v, links)
        if res_d > farthest_d:
            farthest_d = res_d
            farthest_v = res_v
    return farthest_d + 1, farthest_v


def solve(n, links):
    if n == 1:
        return True

    d, v = dfs(0, -1, links)
    d, v = dfs(v, -1, links)
    if (d + 1) % 3 == 0:
        return False
    return True


n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('First' if solve(n, links) else 'Second')

Submission status: Runtime Error

Solution code:
// --------------------------------------------------<TEMPLATE>--------------------------------------------------
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

// -------------------</optimizations>--------------------

// ---------------<Headers and namespaces>----------------
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;

// ---------------</Headers and namespaces>---------------

// -----------------<Defines and typedefs>----------------
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the iterator to kth largest element.(0-based)

typedef long long ll;
typedef long double LD;
#define int ll
#define double LD
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))

// -----<SCANF>-----
#define sfi(x) scanf("%d",&x);
#define sfi2(x,y) scanf("%d%d",&x,&y);
#define sfi3(x,y,z) scanf("%d%d%d",&x,&y,&z);

#define sfl(x) scanf("%lld",&x);
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
#define sfl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z);

#define sfs(x) scanf("%s",x);
#define sfs2(x,y) scanf("%s%s",x,y);
#define sfs3(x,y,z) scanf("%s%s%s",x,y,z);
// ----</SCANF>-----

// ----<PRINTF>-----
#define pfi(x) printf("%d\n",x);
#define pfi2(x,y) printf("%d %d\n",x,y);
#define pfi3(x,y,z) printf("%d %d %d\n",x,y,z);

#define pfl(x) printf("%lld\n",x);
#define pfl2(x,y) printf("%lld %lld\n",x,y);
#define pfl3(x,y,z) printf("%lld %lld %lld\n",x,y,z);

#define pfs(x) printf("%s\n",x);
#define pfs2(x,y) printf("%s %s\n",x,y);
#define pfs3(x,y,z) printf("%s %s %s\n",x,y,z);
// ----</PRINTF>----

#define FLSH fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x) cout << fixed << setprecision(x); 
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// ----------------</Defines and typedefs>----------------

// -------------------<Debugging stuff>-------------------
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

// ------------------</Debugging stuff>-------------------

// ------------------------<Consts>-----------------------
const int MAXN = 1000005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);
const int INF = 1000000000;
const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;

// -----------------------</Consts>-----------------------

// -------------------------<RNG>-------------------------
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.

// ------------------------</RNG>-------------------------

// -----------------<Modular Arithmetic>------------------
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
int add(int a, int b, int c){int res=a+b;return(res>=c?res-c:res);}
int mod_neg(int a, int b, int c){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
int mul(int a, int b, int c){ll res=(ll)a*b;return(res>=c?res%c:res);}
ll mulmod(ll a,ll b, ll m){ll q = (ll)(((LD)a*(LD)b)/(LD)m);ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
template<typename T>T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
template<typename T>T power(T e, T n, T m){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T>T mod_inverse(T a, T n){T x,y,z=0;T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}

// -----------------</Modular Arithmetic>-----------------
// --------------------------------------------------</TEMPLATE>--------------------------------------------------

void solvethetestcase();

signed main(){
	// (UNCOMMENT FOR CIN/COUT) \
	FAST_IO
	PRECISION(10)

	int t = 1;
	// (UNCOMMENT FOR MULTIPLE TEST CASES) \
	sfl(t);
	FOR(testcase,1,t+1){
		// (UNCOMMENT FOR CODEJAM) \
		printf("Case #%lld: ",testcase); 
		solvethetestcase();
	}
}   

int h,w,n;
int x,y;
string a,b;

void solvethetestcase(){
	cin >> h >> w >> n;
	cin >> x >> y;
	cin >> a >> b;
	int l1 = 0,r1 = 0,u1 = 0,d1 = 0,l2 = 0,r2 = 0,u2 = 0,d2 = 0;
	REP(i,n){
		if(a[i] == 'L') l1++;
		if(a[i] == 'R') r1++;
		if(a[i] == 'U') u1++;
		if(a[i] == 'D') d1++;

		if(b[i] == 'L') l2++;
		if(b[i] == 'R') r2++;
		if(b[i] == 'U') u2++;
		if(b[i] == 'D') d2++;

		if(y+r1-l2 > w or y-l1+r2 < 1 or x+d1-u2 > h or x-u1+d2 < 1){
			cout << "NO\n";
			return;
		} 
		remin(l2,min(y-l1+r2-1,y-1));
		remin(r2,min(w+l2-r1-y,w-y));
		remin(u2,min(h+u2-d1-x,x-1));
		remin(d2,min(x-u1+d2-1,h-x));
		if(y+r1-l2 > w or y-l1+r2 < 1 or x+d1-u2 > h or x-u1+d2 < 1){
			cout << "NO\n";
			return;
		} 
	}
	cout << "YES\n";
}