from collections import deque
def main():
data = list(map(int, input().split()))
data = [x - 1 for x in data]
n, k, l = data[:3]
n += 1
k += 1
l += 1
teleports = []
walls = set()
index = 3
for _ in range(k):
arr1 = tuple(data[index:index+3])
arr2 = tuple(data[index+3:index+6])
teleports.append((arr1, arr2))
index += 6
for _ in range(l):
walls.add(tuple(data[index:index+3]))
index += 3
start_cords = tuple(data[index:index+3])
index += 3
goal_cords = tuple(data[index:index+3])
directions = [(-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1)]
deck = deque([(start_cords, 0)])
visited = set()
visited.add(start_cords)
while deck:
curr, dist = deck.popleft()
x,y,z = curr
if curr == goal_cords:
print(dist)
return
for teleport_pair in teleports:
linked_teleport = None
if curr == teleport_pair[0]:
linked_teleport = teleport_pair[1]
elif curr == teleport_pair[1]:
linked_teleport = teleport_pair[0]
if linked_teleport and linked_teleport not in visited:
visited.add(linked_teleport)
deck.appendleft((linked_teleport, dist))
for dx, dy, dz in directions:
new_x, new_y, new_z = x + dx, y + dy, z + dz
if 0 <= new_x < n and 0 <= new_y < n and 0 <= new_z < n:
neybor = (new_x, new_y, new_z)
if neybor not in walls and neybor not in visited:
visited.add(neybor)
deck.append((neybor, dist + 1))
print(-1)
main()
ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKCmRlZiBtYWluKCk6CiAgICBkYXRhID0gbGlzdChtYXAoaW50LCBpbnB1dCgpLnNwbGl0KCkpKQogICAgZGF0YSA9IFt4IC0gMSBmb3IgeCBpbiBkYXRhXQoKICAgIG4sIGssIGwgPSBkYXRhWzozXQogICAgbiArPSAxCiAgICBrICs9IDEKICAgIGwgKz0gMQoKICAgIHRlbGVwb3J0cyA9IFtdCiAgICB3YWxscyA9IHNldCgpCiAgICAKICAgIGluZGV4ID0gMwogICAgZm9yIF8gaW4gcmFuZ2Uoayk6CiAgICAgICAgYXJyMSA9IHR1cGxlKGRhdGFbaW5kZXg6aW5kZXgrM10pCiAgICAgICAgYXJyMiA9IHR1cGxlKGRhdGFbaW5kZXgrMzppbmRleCs2XSkKICAgICAgICB0ZWxlcG9ydHMuYXBwZW5kKChhcnIxLCBhcnIyKSkKICAgICAgICBpbmRleCArPSA2CgogICAgZm9yIF8gaW4gcmFuZ2UobCk6CiAgICAgICAgd2FsbHMuYWRkKHR1cGxlKGRhdGFbaW5kZXg6aW5kZXgrM10pKQogICAgICAgIGluZGV4ICs9IDMKCiAgICBzdGFydF9jb3JkcyA9IHR1cGxlKGRhdGFbaW5kZXg6aW5kZXgrM10pCiAgICBpbmRleCArPSAzCiAgICBnb2FsX2NvcmRzID0gdHVwbGUoZGF0YVtpbmRleDppbmRleCszXSkKCiAgICBkaXJlY3Rpb25zID0gWygtMSwgMCwgMCksICgxLCAwLCAwKSwgKDAsIC0xLCAwKSwgKDAsIDEsIDApLCAoMCwgMCwgLTEpLCAoMCwgMCwgMSldCgogICAgZGVjayA9IGRlcXVlKFsoc3RhcnRfY29yZHMsIDApXSkKICAgIHZpc2l0ZWQgPSBzZXQoKQogICAgdmlzaXRlZC5hZGQoc3RhcnRfY29yZHMpCgogICAgd2hpbGUgZGVjazoKICAgICAgICBjdXJyLCBkaXN0ID0gZGVjay5wb3BsZWZ0KCkKICAgICAgICB4LHkseiA9IGN1cnIKICAgICAgICAKICAgICAgICBpZiBjdXJyID09IGdvYWxfY29yZHM6CiAgICAgICAgICAgIHByaW50KGRpc3QpCiAgICAgICAgICAgIHJldHVybgoKICAgICAgICBmb3IgdGVsZXBvcnRfcGFpciBpbiB0ZWxlcG9ydHM6CiAgICAgICAgICAgIGxpbmtlZF90ZWxlcG9ydCA9IE5vbmUKICAgICAgICAgICAgaWYgY3VyciA9PSB0ZWxlcG9ydF9wYWlyWzBdOgogICAgICAgICAgICAgICAgbGlua2VkX3RlbGVwb3J0ID0gdGVsZXBvcnRfcGFpclsxXQogICAgICAgICAgICBlbGlmIGN1cnIgPT0gdGVsZXBvcnRfcGFpclsxXToKICAgICAgICAgICAgICAgIGxpbmtlZF90ZWxlcG9ydCA9IHRlbGVwb3J0X3BhaXJbMF0KICAgICAgICAKICAgICAgICAgICAgaWYgbGlua2VkX3RlbGVwb3J0IGFuZCBsaW5rZWRfdGVsZXBvcnQgbm90IGluIHZpc2l0ZWQ6CiAgICAgICAgICAgICAgICB2aXNpdGVkLmFkZChsaW5rZWRfdGVsZXBvcnQpCiAgICAgICAgICAgICAgICBkZWNrLmFwcGVuZGxlZnQoKGxpbmtlZF90ZWxlcG9ydCwgZGlzdCkpCiAgICAgICAgICAgIAogICAgICAgIGZvciBkeCwgZHksIGR6IGluIGRpcmVjdGlvbnM6CiAgICAgICAgICAgIG5ld194LCBuZXdfeSwgbmV3X3ogPSB4ICsgZHgsIHkgKyBkeSwgeiArIGR6CiAgICAgICAgICAgIGlmIDAgPD0gbmV3X3ggPCBuIGFuZCAwIDw9IG5ld195IDwgbiBhbmQgMCA8PSBuZXdfeiA8IG46CiAgICAgICAgICAgICAgICBuZXlib3IgPSAobmV3X3gsIG5ld195LCBuZXdfeikKICAgICAgICAgICAgICAgIGlmIG5leWJvciBub3QgaW4gd2FsbHMgYW5kIG5leWJvciBub3QgaW4gdmlzaXRlZDoKICAgICAgICAgICAgICAgICAgICB2aXNpdGVkLmFkZChuZXlib3IpCiAgICAgICAgICAgICAgICAgICAgZGVjay5hcHBlbmQoKG5leWJvciwgZGlzdCArIDEpKQogICAgICAgICAgICAgICAgCiAgICBwcmludCgtMSkKCm1haW4oKQ==