unionfind:
    push rbp
    mov rbp, rsp
    push rsp
    push rbx
    push r12
    push r13
    push r14
    push r15


    #rbx = n, r12= instructionString, r13 = solutionString
    mov rbx, rdi
    mov r12, rsi
    mov r13, rdx

    #r14 = array of elements, r15 = array of size of elements
    mov rdi, rbx
    imul rdi, rdi, 8
    call malloc
    mov r14, rax

    mov rdi, rbx
    imul rdi, rdi, 8
    call malloc
    mov r15, rax

    #initialize array of elements and array of size
    mov rax, rbx

    init:
      dec rax
      cmp rax, 0
      jl continue_with_reading
      mov qword ptr [r14 + rax * 8], rax
      mov qword ptr [r15 + rax * 8], 1
      jmp init

    #Read instruction
    continue_with_reading:
      xor rdi, rdi
      mov dil, byte ptr [r12]
      cmp dil, 70
      je F
      cmp dil, 85
      je U
      jmp ende

    #---------------------------------- Functionality -------------------------------------------

    F:
      # Write 'F'
      mov rdi, 70
      mov rsi, r13
      call putint
      mov r13, rax

      # Read char number and transform it to int64
      inc r12
      mov rdi, r12
      call getint
      call find

      # Write representant (in rax) to solution, 'L' and number of levels in rcx
      push rcx #save it bc it can be changed by putint

      mov rdi, rax
      mov rsi, r13
      call putint
      mov r13, rax

      mov rdi, 76
      mov rsi, r13
      call putint
      mov r13, rax

      pop rcx
      mov rdi, rcx
      mov rsi, r13
      call putint
      mov r13, rax

      jmp continue_with_reading


    U:
      # Write 'U'
      mov rdi, 85
      mov rsi, r13
      call putint
      mov r13, rax

      # Read first char number and transform it to int64
      inc r12
      mov rdi, r12
      call getint
      call find
      push rax #Representant 1 of rax
      push rcx #levels first tree

      # Read second char number and transform it to int64
      inc r12 #skips '&'
      mov rdi, r12
      call getint
      call find # representant 2 in rax, levels of second tree in rcx

      pop rdx #get levels
      add rcx, rdx #total num of levels

      pop rdx #Representant 1
      cmp rdx, rax
      je nodes_in_same_tree
      mov rdi, [r15 + rdx * 8] #save num of elements of 1st tree in rdi
      cmp rdi, [r15 + rax * 8] #compare num of elements of both trees. RDX one is first tree
      jge union_left
      jmp union_right

    nodes_in_same_tree:

      #write group representant
      mov rdi, rdx
      mov rsi, r13
      call putint
      mov r13, rax

      #write 'L'
      mov rdi, 76
      mov rsi, r13
      call putint
      mov r13, rax

      #Write levels
      mov rdi, rcx
      mov rsi, r13
      call putint
      mov r13, rax

      jmp continue_with_reading

    union_left:
      mov qword ptr [r14 + rax * 8], rdx #unify right tree to left tree (change of representant)
      add rdi, qword ptr [r15 + rax * 8] #add number of elements of first tree with num of elements of second tree
      mov qword ptr [r15 + rdx * 8], rdi #save new num of elements in representant of first tree
      mov qword ptr [r15 + rax * 8], 0

      #write group representant
      mov rdi, rdx
      mov rsi, r13
      call putint
      mov r13, rax

      #write 'L'
      mov rdi, 76
      mov rsi, r13
      call putint
      mov r13, rax

      #Write levels
      mov rdi, rcx
      mov rsi, r13
      call putint
      mov r13, rax

      jmp continue_with_reading


    union_right:
      mov qword ptr [r14 + rdx * 8], rax
      add rdi, qword ptr [r15 + rax * 8]
      mov qword ptr [r15 + rdx * 8], 0
      mov qword ptr [r15 + rax * 8], rdi

      #write group representant
      mov rdi, rax
      mov rsi, r13
      call putint
      mov r13, rax

      #write 'L'
      mov rdi, 76
      mov rsi, r13
      call putint
      mov r13, rax

      #Write levels
      mov rdi, rcx
      mov rsi, r13
      call putint
      mov r13, rax

      jmp continue_with_reading


    #params: rax = 64bit integer number from instruction, return value: rax = representant, rcx = levels
    find:
        push rbp
        mov rbp, rsp
        push rsp

      xor rcx, rcx
      xor rdx, rdx
      xor rdi, rdi

      # num which we search its representant
      mov rdx, rax

      loop_array:
      cmp rax, qword ptr [r14 + rax * 8]
      je relink
      inc rcx
      mov rax, qword ptr [r14 + rax * 8]
      jmp loop_array

      # rax = representant, rdx = original num, rdi = temporal variable
      relink:
      cmp qword ptr [r14 + rdx * 8], rax
      je end_find
      mov rdi, qword ptr [r14 + rdx * 8]
      mov qword ptr [r14 + rdx * 8], rax
      mov rdx, rdi
      jmp relink

      end_find:

      pop rsp
      pop rbp
      ret


    ende:
      #null byte in solution string
      mov rdi, 0
      mov rsi, r13
      call putint

      pop r15
      pop r14
      pop r13
      pop r12
      pop rbx
      pop rsp
      pop rbp

      ret